---
_id: '18196'
abstract:
- lang: eng
  text: 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:
- first_name: Martin
  full_name: Ziegler, Martin
  last_name: Ziegler
citation:
  ama: 'Ziegler M. Quasi-optimal Arithmetic for Quaternion Polynomials. In: <i>Proc.
    14th Annual International Symposium on Algorithms and Computation (ISAAC’03)</i>.
    Lecture Notes in Computer Science, vol 2906. Springer, Berlin, Heidelberg. ; 2003:705-715.
    doi:<a href="https://doi.org/10.1007/978-3-540-24587-2_72">10.1007/978-3-540-24587-2_72</a>'
  apa: Ziegler, M. (2003). Quasi-optimal Arithmetic for Quaternion Polynomials. In
    <i>Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC’03)</i>
    (pp. 705–715). <a href="https://doi.org/10.1007/978-3-540-24587-2_72">https://doi.org/10.1007/978-3-540-24587-2_72</a>
  bibtex: '@inproceedings{Ziegler_2003, series={Lecture Notes in Computer Science,
    vol 2906. Springer, Berlin, Heidelberg}, title={Quasi-optimal Arithmetic for Quaternion
    Polynomials}, DOI={<a href="https://doi.org/10.1007/978-3-540-24587-2_72">10.1007/978-3-540-24587-2_72</a>},
    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} }'
  chicago: Ziegler, Martin. “Quasi-Optimal Arithmetic for Quaternion Polynomials.”
    In <i>Proc. 14th Annual International Symposium on Algorithms and Computation
    (ISAAC’03)</i>, 705–15. Lecture Notes in Computer Science, Vol 2906. Springer,
    Berlin, Heidelberg, 2003. <a href="https://doi.org/10.1007/978-3-540-24587-2_72">https://doi.org/10.1007/978-3-540-24587-2_72</a>.
  ieee: M. Ziegler, “Quasi-optimal Arithmetic for Quaternion Polynomials,” in <i>Proc.
    14th Annual International Symposium on Algorithms and Computation (ISAAC’03)</i>,
    2003, pp. 705–715.
  mla: Ziegler, Martin. “Quasi-Optimal Arithmetic for Quaternion Polynomials.” <i>Proc.
    14th Annual International Symposium on Algorithms and Computation (ISAAC’03)</i>,
    2003, pp. 705–15, doi:<a href="https://doi.org/10.1007/978-3-540-24587-2_72">10.1007/978-3-540-24587-2_72</a>.
  short: 'M. Ziegler, in: Proc. 14th Annual International Symposium on Algorithms
    and Computation (ISAAC’03), 2003, pp. 705–715.'
date_created: 2020-08-24T14:18:19Z
date_updated: 2022-01-06T06:53:27Z
department:
- _id: '63'
doi: 10.1007/978-3-540-24587-2_72
language:
- iso: eng
page: 705-715
publication: Proc. 14th Annual International Symposium on Algorithms and Computation
  (ISAAC'03)
publication_identifier:
  isbn:
  - '9783540206958'
  - '9783540245872'
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
series_title: Lecture Notes in Computer Science, vol 2906. Springer, Berlin, Heidelberg
status: public
title: Quasi-optimal Arithmetic for Quaternion Polynomials
type: conference
user_id: '15415'
year: '2003'
...