Quasi-optimal Arithmetic for Quaternion Polynomials

M. Ziegler, in: Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC’03), 2003, pp. 705–715.

Download
No fulltext has been uploaded.
Conference Paper | Published | English
Author
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.
Publishing Year
Proceedings Title
Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC'03)
Page
705-715
LibreCat-ID

Cite this

Ziegler M. Quasi-optimal Arithmetic for Quaternion Polynomials. In: Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC’03). Lecture Notes in Computer Science, vol 2906. Springer, Berlin, Heidelberg. ; 2003:705-715. doi:10.1007/978-3-540-24587-2_72
Ziegler, M. (2003). Quasi-optimal Arithmetic for Quaternion Polynomials. In Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC’03) (pp. 705–715). https://doi.org/10.1007/978-3-540-24587-2_72
@inproceedings{Ziegler_2003, series={Lecture Notes in Computer Science, vol 2906. Springer, Berlin, Heidelberg}, title={Quasi-optimal Arithmetic for Quaternion Polynomials}, DOI={10.1007/978-3-540-24587-2_72}, booktitle={Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC’03)}, author={Ziegler, Martin}, year={2003}, pages={705–715}, collection={Lecture Notes in Computer Science, vol 2906. Springer, Berlin, Heidelberg} }
Ziegler, Martin. “Quasi-Optimal Arithmetic for Quaternion Polynomials.” In Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC’03), 705–15. Lecture Notes in Computer Science, Vol 2906. Springer, Berlin, Heidelberg, 2003. https://doi.org/10.1007/978-3-540-24587-2_72.
M. Ziegler, “Quasi-optimal Arithmetic for Quaternion Polynomials,” in Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC’03), 2003, pp. 705–715.
Ziegler, Martin. “Quasi-Optimal Arithmetic for Quaternion Polynomials.” Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC’03), 2003, pp. 705–15, doi:10.1007/978-3-540-24587-2_72.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search