Efficient Evaluation of Matrix Polynomials beyond the Paterson–Stockmeyer Method
Abstract
:1. Introduction
- Evaluating polynomial approximations of matrix functions of degrees 15 and 21 with cost and , respectively.
- Evaluating matrix polynomials of degrees with with cost .
- Evaluating matrix polynomials of degrees greater than 30 with two matrix products less than the Paterson–Stockmeyer method.
2. Efficient Evaluation of Matrix Polynomials
2.1. Paterson–Stockmeyer Method
2.2. General Polynomial Evaluation Methods beyond the Paterson–Stockmeyer Method
3. Three General Expressions for
3.1. Evaluation of Matrix Polynomial Approximations of Order 15 with ,
3.2. Evaluation of Matrix Polynomial Approximations of Order 21
3.3. Evaluation of Matrix Polynomials of Degree
- a.
- b.
- c.
- d.
- In the following, we show that (71) holds. Taking (16) and (17) into account, one getsSince condition (69) is fulfilled, then by (76), one gets that condition (18) is also fulfilled. Then, polynomial from (65) can be effectively computed using (16) and (17), and by (76) and (77), one gets that and depend on , i.e.,Equating the terms of degree in (75), we obtainTherefore,Proceeding in an analogous way with for , we obtainSinceEquating the terms of degree in (66) and taking (82) into account, we obtain
- In the following, we show that (72) holds. Equating the terms of degree in (66) and taking condition from (77) into account, we obtainHence, taking (71) into account, it follows thatHence, using (87), one gets
- In the following, we show that (73) holds. Equating the terms of degree in (66) and taking condition from (77) into account, it follows thatEquating the terms of degree in (66) and condition , one gets
- In the following, we show that (74) holds. Equating the terms of degree in (66) and takingcondition into account, it follows thatEquating the terms of degree in (66) and condition , we obtain
- The Paterson–Stockmeyer evaluation formula.
4. Conclusions
Author Contributions
Funding
Institutional Review Board Statement
Informed Consent Statement
Data Availability Statement
Conflicts of Interest
Abbreviations
MDPI | Multidisciplinary Digital Publishing Institute |
DOAJ | Directory of open access journals |
TLA | Three letter acronym |
LD | Linear dichroism |
References
- Sastre, J. Efficient evaluation of matrix polynomials. Linear Algebra Appl. 2018, 539, 229–250. [Google Scholar] [CrossRef]
- Paterson, M.S.; Stockmeyer, L.J. On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM J. Comput. 1973, 2, 60–66. [Google Scholar] [CrossRef] [Green Version]
- Higham, N.J. Functions of Matrices: Theory and Computation; Society for Industrial and Applied Mathematics: Philadelphia, PA, USA, 2008. [Google Scholar]
- Sastre, J.; Ibáñez, J.; Alonso, P.; Peinado, J.; Defez, E. Fast taylor polynomial evaluation for the computation of the matrix cosine. J. Comput. Appl. Math. 2019, 354, 641–650. [Google Scholar] [CrossRef]
- Sastre, J.; Ibáñez, J.E. Defez, Boosting the computation of the matrix exponential. Appl. Math. Comput. 2019, 340, 206–220. [Google Scholar]
- Al-Mohy, A.H.; Higham, N.J. A new scaling and squaring algorithm for the matrix exponential. SIAM J. Matrix Anal. Appl. 2009, 31, 970–989. [Google Scholar] [CrossRef] [Green Version]
- Al-Mohy, A.H.; Higham, N.J.; Relton, S. New Algorithms for Computing the Matrix Sine and Cosine Separately or Simultaneously. SIAM J. Sci. Comput. 2015, 37, A456–A487. [Google Scholar] [CrossRef] [Green Version]
- Bader, P.; Blanes, S.; Casas, F. Computing the Matrix Exponential with an Optimized Taylor Polynomial Approximation. Mathematics 2019, 7, 1174. [Google Scholar] [CrossRef] [Green Version]
- Bader, P.; Blanes, S.; Casas, F. An improved algorithm to compute the exponential of a matrix. arXiv 2017, arXiv:1710.10989. [Google Scholar]
- Sastre, J. On the Polynomial Approximation of Matrix Functions. Available online: http://personales.upv.es/~jorsasma/AMC-S-16-00951.pdf (accessed on 20 April 2020).
- Al-Mohy, A.H.; Higham, N.J. Improved inverse scaling and squaring algorithms for the matrix logarithm. SIAM J. Sci. Comput. 2012, 34, C153–C169. [Google Scholar] [CrossRef] [Green Version]
- Moler, C.B.; Loan, C.V. Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Rev. 2003, 45, 3–49. [Google Scholar] [CrossRef]
- Blackford, S.; Dongarra, J. Installation Guide for LAPACK, LAPACK Working Note 41. Available online: http://www.netlib.org/lapack/lawnspdf/lawn41.pdf (accessed on 20 April 2020).
- Sastre, J. Efficient mixed rational and polynomial approximation of matrix functions. Appl. Math. Comput. 2012, 218, 11938–11946. [Google Scholar] [CrossRef]
- Sastre, J.; Ibáñez, J.; Alonso, P.; Peinado, J.; Defez, E. Two algorithms for computing the matrix cosine function. Appl. Math. Comput. 2017, 312, 66–77. [Google Scholar] [CrossRef] [Green Version]
- Fasi, M. Optimality of the Paterson–Stockmeyer method for evaluating matrix polynomials and rational matrix functions. Linear Algebra Appl. 2019, 574, 182–200. [Google Scholar] [CrossRef] [Green Version]
- Ibáñez, J.; Alonso, J.M.; Sastre, J.; Defez, E.; Alonso-Jordá, P. Advances in the Approximation of the Matrix Hyperbolic Tangent. Mathematics 2021, 9, 1219. [Google Scholar] [CrossRef]
- Higham, N.J. The Matrix Computation Toolbox. Available online: http://www.ma.man.ac.uk/~higham/mctoolbox (accessed on 18 April 2020).
- Davies, E.B. Approximate diagonalization. SIAM J. Matrix Anal. Appl. 2007, 29, 1051–1064. [Google Scholar] [CrossRef] [Green Version]
- Higham, N. Matrix Logarithm. 2020. Available online: https://www.mathworks.com/matlabcentral/fileexchange/33393-matrix-logarithm (accessed on 18 April 2020).
3.571998478323090 | −2.645687940516643 | ||
−1.857982456862233 | 1.049722718717408 | ||
3.278753597700932 | 8.965376033761624 | ||
−1.148774768780758 | −1.859420533601965 | ||
−2.008741312156575 | 1.493008139094410 | ||
1.737292932136998 | 1.570135323717639 | ||
6.982819862335600 | −1/6! | ||
−5.259287265295055 | 1/4! |
2.475376717210241 | −1.035631527011582 | ||
2.440262449961976 | −3.416046999733390 | ||
1.674278428631194 | 4.544910328432021 | ||
−9.742340743664729 | 2.741820014945195 | ||
−4.744919764579607 | −1.601466804001392 | ||
5.071515307996127 | 1.681067607322385 | ||
2.025389951302878 | 7.526271076306975 | ||
−4.809463272682823 | 4.282509402345739 | ||
6.574533191427105 | 1.462562712251202 | ||
3.236650728737168 | 5.318525879522635 |
3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |
---|---|---|---|---|---|---|---|---|---|---|---|
6 | 9 | 12 | 16 | 20 | 25 | 30 | 36 | 42 | 49 | 56 | |
8 | 12 | 16 | 20 | 25 | 30 | 36 | 42 | 49 | 56 | 64 | |
- | 12 | 18 | 24 | 30 | 36 | 42 | 49 | 56 | 64 | 72 | |
- | 2 | 3 | 4 | 5 | 6 | 6 | 7 | 7 | 8 | 8 | |
- | 0 | 0 | 0 | 0 | 0 | 6 | 7 | 14 | 16 | 24 |
3.218297948685432 | 2.231079274704953 | ||
1.109757913339804 | 3.891001336083639 | ||
7.667169819995447 | 6.539646241763075 | ||
6.192062222365700 | 8.543283349051067 | ||
5.369406358130299 | −1.642222074981266 | ||
2.156719633283115 | 6.179507508449100 | ||
−2.827270631646985 | 3.176715034213954 | ||
−1.299375958233227 | 8.655952402393143 | ||
−3.345609833413695 | 3.035900161106295 | ||
−8.193390302418316 | 9.404049154527467 | ||
−1.318571680058333 | −2.182842624594848 | ||
1.318536866523954 | −5.036471128390267 | ||
1.718006767617093 | −4.650956099599815 | ||
1.548174815648151 | 5.154435371157740 | ||
2.139947460365092 | 1 |
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. |
© 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Sastre, J.; Ibáñez, J. Efficient Evaluation of Matrix Polynomials beyond the Paterson–Stockmeyer Method. Mathematics 2021, 9, 1600. https://doi.org/10.3390/math9141600
Sastre J, Ibáñez J. Efficient Evaluation of Matrix Polynomials beyond the Paterson–Stockmeyer Method. Mathematics. 2021; 9(14):1600. https://doi.org/10.3390/math9141600
Chicago/Turabian StyleSastre, Jorge, and Javier Ibáñez. 2021. "Efficient Evaluation of Matrix Polynomials beyond the Paterson–Stockmeyer Method" Mathematics 9, no. 14: 1600. https://doi.org/10.3390/math9141600
APA StyleSastre, J., & Ibáñez, J. (2021). Efficient Evaluation of Matrix Polynomials beyond the Paterson–Stockmeyer Method. Mathematics, 9(14), 1600. https://doi.org/10.3390/math9141600