A binary powering Schur algorithm for computing primary matrix roots. (English) Zbl 1202.65053

The authors propose a new algorithm based on the Schur normal form, for computing a primary \(p\)th root of an \(n \times n\) complex matrix. They prove that the cost of the proposed algorithm is lowered to \({\mathcal{O}}(n^2 p + n^3 \log_2 p)\) ops and the storage is lowered to \({\mathcal{O}}(n p + n^2 \log_2 p)\) real numbers.


65F30 Other matrix algorithms (MSC2010)
15A24 Matrix equations and identities
15A16 Matrix exponential and similar functions of matrices


mftoolbox; mctoolbox
Full Text: DOI


[1] Björck, Å., Hammarling, S.: A Schur method for the square root of a matrix. Linear Algebra Appl. 52/53, 127–140 (1983) · Zbl 0515.65037
[2] Denman, E.D., Beavers, A.N., Jr.: The matrix sign function and computations in systems. Appl. Math. Comput. 2(1), 63–94 (1976) · Zbl 0398.65023
[3] Guo, C.-H.: On Newton’s method and Halley’s method for the principal pth root of a matrix. Linear Algebra Appl. (2009, in press)
[4] Guo, C.-H., Higham, N.J.: A Schur–Newton method for the matrix pth root and its inverse. SIAM J. Matrix Anal. Appl. 28(3), 788–804 (2006) · Zbl 1128.65030
[5] Higham, N.J.: The Matrix Function Toolbox. http://www.ma.man.ac.uk/\(\sim\)higham/mctoolbox (Retrieved on November 3, 2009)
[6] Higham, N.J.: Newton’s method for the matrix square root. Math. Comput. 46(174), 537–549 (1986) · Zbl 0614.65045
[7] Higham, N.J.: Computing real square roots of a real matrix. Linear Algebra Appl. 88/89, 405–430 (1987) · Zbl 0625.65032
[8] Higham, N.J.: Functions of matrices: theory and computation. Society for Industrial and Applied Mathematics, Philadelphia (2008) · Zbl 1167.15001
[9] Higham, N.J., Lin, L.: On pth roots of stochastic matrices. MIMS EPrint 2009.21, Manchester Institute for Mathematical Sciences, The University of Manchester, UK (2009)
[10] Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1994) (Corrected reprint of the 1991 original) · Zbl 0801.15001
[11] Iannazzo, B.: A note on computing the matrix square root. Calcolo 40(4), 273–283 (2003) · Zbl 1117.65059
[12] Iannazzo, B.: On the Newton method for the matrix pth root. SIAM J. Matrix Anal. Appl. 28(2), 503–523 (2006) · Zbl 1113.65054
[13] Iannazzo, B.: A family of rational iterations and its application to the computation of the matrix pth root. SIAM J. Matrix Anal. Appl. 30(4), 1445–1462 (2008) · Zbl 1176.65054
[14] Laasonen, P.: On the iterative solution of the matrix equation AX 2 I = 0. Math. Tables Other Aids Comput. 12, 109–116 (1958) · Zbl 0083.11704
[15] Laszkiewicz, B., Zietak, K.: Algorithms for the matrix sector function. Electron. Trans. Numer. Anal. 31, 358–383 (2008) · Zbl 1190.65069
[16] Laszkiewicz, B., Zietak, K: A Padé family of iterations for the matrix sector function and the matrix pth root. Numer. Linear Alg. Appl. 16(11–12), 951–970 (2009) · Zbl 1224.65123
[17] Meini, B.: The matrix square root from a new functional perspective: theoretical results and computational issues. SIAM J. Matrix Anal. Appl. 26(2), 362–376 (2004/05) · Zbl 1087.15019
[18] Smith, M.I.: A Schur algorithm for computing matrix pth roots. SIAM J. Matrix Anal. Appl. 24(4), 971–989 (2003) · Zbl 1040.65038
[19] Smith, M.I.: Numerical Computation of Matrix Functions. PhD thesis, University of Manchester, Manchester, England (2002)
[20] http://bezout.dm.unipi.it/software (Retrieved on November 3, 2009)
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.