@inproceedings{18196,
  abstract     = {{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.}},
  author       = {{Ziegler, Martin}},
  booktitle    = {{Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC'03)}},
  isbn         = {{9783540206958}},
  issn         = {{0302-9743}},
  pages        = {{705--715}},
  title        = {{{Quasi-optimal Arithmetic for Quaternion Polynomials}}},
  doi          = {{10.1007/978-3-540-24587-2_72}},
  year         = {{2003}},
}