Quasi-Optimal Arithmetic for Quaternion Polynomials
<|reference_start|>Quasi-Optimal Arithmetic for Quaternion Polynomials: 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.<|reference_end|>
@article{ziegler2003quasi-optimal,
    title={Quasi-Optimal Arithmetic for Quaternion Polynomials},
    author={Martin Ziegler},
    journal={pp.705-715 in Proc.14th ISAAC (2003), Springer LNCS 2906},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0304004},
    primaryClass={cs.SC}
}