TY - CONF AB - 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, 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 fields R and C to the SKEW-field H of quaternions is promising but still missing. The present work proposes three approaches 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. AU - Ziegler, Martin ID - 18196 SN - 0302-9743 T2 - Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC'03) TI - Quasi-optimal Arithmetic for Quaternion Polynomials ER -