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.
A structural similarity between Classical Mechanics (CM) and Quantum Mechanics (QM) was revealed by P.A.M. Dirac in terms of Lie Algebras: while in CM the dynamics is determined by the Lie algebra of Poisson brackets on the manifold of scalar fields for classical position/momentum observables q/p, d/dt q={q,H}, d/dt p={p,H}, QM evolves (in Heisenberg's picture) according to the formally similar Lie algebra of commutator brackets of the corresponding operators Q/P: d/dt Q=i/h [Q,H], d/dt P=i/h [P,H] where QP-PQ=ih. A further common framework for comparing CM and QM is the category of symplectic manifolds. Other than previous authors, this paper considers phase space of Heisenberg's picture, i.e., the manifold of pairs of operator observables (Q,P) satisfying commutation relation. On a sufficiently high algebraic level of abstraction -- which we believe to be of interest on its own -- it turns out that this approach leads to a truly NON-linear yet Hamiltonian reformulation of QM evolution.