Quasi-Optimal Arithmetic for Quaternion Polynomials
| dc.creator | Ziegler, Martin | |
| dc.date | 2003-04-01 | |
| dc.date | 2004-01-02 | |
| dc.date.accessioned | 2026-07-07T03:19:34Z | |
| dc.date.available | 2026-07-07T03:19:34Z | |
| dc.description | Fast algorithms for arithmetic on real or complex polynomials are well-known and have proven to be not only asymptotically efficient but also very practical. Based on Fast Fourier Transform (FFT), they for instance multiply two polynomials of degree up to N or multi-evaluate one at N points simultaneously within quasi-linear time O(N.polylog N). An extension to (and in fact the mere definition of) polynomials over the skew-field H of quaternions is promising but still missing. The present work proposes three such definitions which in the commutative case coincide but for H turn out to differ, each one satisfying some desirable properties while lacking others. For each notion we devise algorithms for according arithmetic; these are quasi-optimal in that their running times match lower complexity bounds up to polylogarithmic factors. | |
| dc.description | published version (11 pages) plus appendix (2 pages) | |
| dc.identifier | https://arxiv.org/abs/cs/0304004 | |
| dc.identifier | http://arxiv.org/abs/cs/0304004 | |
| dc.identifier | pp.705-715 in Proc.14th ISAAC (2003), Springer LNCS 2906 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31512 | |
| dc.subject | Symbolic Computation | |
| dc.subject | I.1;F.2.1 | |
| dc.title | Quasi-Optimal Arithmetic for Quaternion Polynomials | |
| dc.type | text |