zbMATH — the first resource for mathematics

Evaluation schemes in the ring of quaternionic polynomials. (English) Zbl 06858769
Summary: In this paper we focus on computational aspects associated with polynomial problems in the ring of one-sided quaternionic polynomials. The complexity and error bounds of quaternion arithmetic are considered and several evaluation schemes are analyzed from their complexity point of view. The numerical stability of generalized Horner’s and Goertzel’s algorithms to evaluate polynomials with quaternion floating-point coefficients is addressed. Numerical tests illustrate the behavior of the algorithms from the point of view of performance and accuracy.

65Y20 Complexity and performance of numerical algorithms
11R52 Quaternion and other division algebras: arithmetic, zeta functions
12Y05 Computational aspects of field theory and polynomials (MSC2010)
Full Text: DOI
[1] Clenshaw, CW, A note on the summation of Chebyshev series, Math. Comput., 9, 118-120, (1955) · Zbl 0065.05403
[2] Davis, P.J.: Interpolation and Approximation. Blaisdell Publishing Co. Ginn and Co., New York (1963) · Zbl 0111.06003
[3] Falcão, MI; Miranda, F, Quaternions: a Mathematica package for quaternionic analysis, Lect. Notes Comput. Sci., 6784, 200-214, (2011)
[4] Gentleman, WM, An error analysis of goertzel’s (watt’s) method for computing Fourier coefficients, Comput. J., 12, 160-165, (1969) · Zbl 0185.40802
[5] Goertzel, G, An algorithm for the evaluation of finite trigonometric series, Am. Math. Mon., 65, 34-35, (1958) · Zbl 0079.13910
[6] Gordon, B; Motzkin, TS, On the zeros of polynomials over division rings I, Trans. Am. Math. Soc., 116, 218-226, (1965) · Zbl 0141.03002
[7] Graillat, S; Langlois, P; Louvet, N, Algorithms for accurate, validated and fast polynomial evaluation, Jpn. J. Ind. Appl. Math., 26, 191-214, (2009) · Zbl 1184.65029
[8] Graillat, S; Ménissier-Morain, V, Accurate summation, dot product and polynomial evaluation in complex floating point arithmetic, Inf. Comput., 216, 57-71, (2012) · Zbl 1259.65073
[9] Gürlebeck, K., Habetha, K., Sprößig, W.: Holomorphic Functions in the Plane and \(n\)-Dimensional Space. Birkhäuser, Basel (2008) Translated from the 2006 German original · Zbl 1104.30001
[10] Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM, Philadelphia (2002) · Zbl 1011.65010
[11] Jeannerod, C-P; Rump, SM, Improved error bounds for inner products in floating-point arithmetic, SIAM J. Matrix Anal. Appl., 34, 338-344, (2013) · Zbl 1279.65052
[12] Knuth, D.E.: Seminumerical Algorithms, volume 2 of The Art of Computer Programming, 2nd edn. Addison-Wesley, Reading (1981) · Zbl 0477.65002
[13] Lam, T.-Y.: A First Course in Noncommutative Rings. Graduate Texts in Mathematics. Springer, New York (1991) · Zbl 0728.16001
[14] McNamee, J.M.: Numerical Methods for Roots of Polynomials, volume 16 of Part I. Elsevier, Amsterdam (2007) · Zbl 1143.65002
[15] Miranda, F., Falcão, M.I.: QuaternionAnalysis package: user’s guide, technical report (2014). http://w3.math.uminho.pt/QuaternionAnalysis · Zbl 0399.65024
[16] Newbery, ACR, Error analysis for Fourier series evaluation, Math. Comput., 27, 639-644, (1973) · Zbl 0308.65029
[17] Niven, I, Equations in quaternions, Am. Math. Mon., 48, 654-661, (1941) · Zbl 0060.08002
[18] Oliver, J, Rounding error propagation in polynomial evaluation schemes, J. Comput. Appl. Math., 5, 85-97, (1979) · Zbl 0399.65024
[19] Pogorui, A; Shapiro, M, On the structure of the set of zeros of quaternionic polynomials, Complex Var. Theory Appl., 49, 379-389, (2004) · Zbl 1160.30353
[20] Serôdio, R; Siu, L-S, Zeros of quaternion polynomials, Appl. Math. Lett., 14, 237-239, (2001) · Zbl 0979.30030
[21] Smoktunowicz, A; Wróbel, I, On improving the accuracy of horner’s and goertzel’s algorithms, Numer. Algorithms, 38, 243-258, (2005) · Zbl 1075.65034
[22] Wilkinson, J.H.: Rounding Errors in Algebraic Processes. Notes on Applied Science. Majesty’s Stationery Office, London, Prentice-Hall, Englewood Cliffs, NJ, USA (1963) · Zbl 1075.65034
[23] Zhang, F, Quaternions and matrices of quaternions, Linear Algebra Appl., 251, 21-57, (1997) · Zbl 0873.15008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.