×

zbMATH — the first resource for mathematics

Efficient computation of tridiagonal matrices largest eigenvalue. (English) Zbl 1376.65048
Summary: This paper proposes a method for a fast estimation of the largest eigenvalue of an asymmetric tridiagonal matrix. The proposed method is based on the power method and the computation of the square of the original matrix. The matrix square is computed through a proposed fast algorithm designed specifically for tridiagonal matrices. Implementations for compressed column (CCS) and compressed row storage (CRS) formats are provided, discussed and compared to a standard scientific library. We investigate the roundoff numerical errors, showing that the proposed method provides errors no greater than the usual power method. We provide numerical results with simulations in C/C++ implementation in order to demonstrate the effectiveness of the proposed method.

MSC:
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F50 Computational methods for sparse matrices
Software:
GSL; mctoolbox
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Golub, G. H.; Loan, C. F.V., Matrix Computations, (1996), Johns Hopkins University Press Baltimore, MD, USA
[2] Blahut, R. E., Fast Algorithms for Digital Signal Processing, (2010), Cambridge University Press · Zbl 1253.94001
[3] Parker, R. L., Geophysical Inverse Theory, (1994), Princeton University Press · Zbl 0812.35159
[4] Crank, J.; Nicolson, E., A practical method for numerical evaluation of solutions of partial differential equations of the heat-conduction type, Math. Proc. Camb. Phil. Soc., 43, 50-67, (1947) · Zbl 0029.05901
[5] Meurant, G., A review on the inverse of symmetric tridiagonal and block tridiagonal matrices, J. Math. Anal. Appl., 13, 3, 707-728, (1992) · Zbl 0754.65029
[6] Hadj, A. D.A.; Elouafi, M., A fast numerical algorithm for the inverse of a tridiagonal and pentadiagonal matrix, Appl. Math. Comput., 202, 2, 441-445, (2008) · Zbl 1153.65030
[7] El-Mikkawy, M.; Karawia, A., Inversion of general tridiagonal matrices, Appl. Math. Lett., 19, 8, 712-720, (2006) · Zbl 1119.65022
[8] Huang, Y.; McColl, W. F., Analytical inversion of general tridiagonal matrices, J. Phys. A: Math. Gen., 30, 22, 7919, (1997) · Zbl 0927.15003
[9] Björck, Å., (Numerical Methods in Matrix Computations, Texts in Applied Mathematics, (2014), Springer International Publishing)
[10] Demmel, J.; Veselić, K., Jacobis method is more accurate than QR, SIAM J. Matrix Anal. Appl., 13, 4, 1204-1245, (1992) · Zbl 0759.65011
[11] P. Arbenz, Lecture notes on solving large scale eigenvalue problems, (Apr. 2016).
[12] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. Symbolic Comput., 9, 3, 251-280, (1990), Special issue on computational algebraic complexity · Zbl 0702.65046
[13] Davie, A. M.; Stothers, A. J., Improved bound for complexity of matrix multiplication, Proc. Roy. Soc. Edinburgh Math., 143, 2, 351-369, (2013) · Zbl 1276.65024
[14] Gall, F. L., Powers of tensors and fast matrix multiplication, (Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC’14, (2014), ACM New York, NY, USA), 296-303 · Zbl 1325.65061
[15] Robinson, S., Toward an optimal algorithm for matrix multiplication, SIAM News, (2005)
[16] Cuppen, J. J.M., A divide and conquer method for the symmetric tridiagonal eigenproblem, Numer. Math., 36, 2, 177-195, (1980) · Zbl 0431.65022
[17] Krishnakumar, A. S.; Morf, M., Eigenvalues of a symmetric tridiagonal matrix: A divide-and-conquer approach, Numer. Math., 48, 3, 349-368, (1986) · Zbl 0595.65035
[18] Dongarra, J. J.; Sorensen, D. C., A fully parallel algorithm for the symmetric eigenvalue problem, SIAM J. Sci. Stat. Comput., 8, 2, 139-154, (1987)
[19] Gu, M.; Eisenstat, S. C., A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem, SIAM J. Matrix Anal. Appl., 15, 4, 1266-1276, (1994) · Zbl 0807.65029
[20] Gu, M.; Eisenstat, S. C., A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem, SIAM J. Matrix Anal. Appl., 16, 1, 172-191, (1995) · Zbl 0815.65050
[21] Coelho, D. F.G.; Dimitrov, V. S., Fast estimation of tridiagonal matrices largest eigenvalue, (The 30th Annual IEEE Canadian Conference on Electrical and Computer Engineering, (2017), IEEE Windsor, ON, Canada)
[22] Wilkinson, J. H., Rounding Errors in Algebraic Processes, (1963), Dover Publications Inc. · Zbl 1041.65502
[23] Higham, N. J., Accuracy and stability of numerical algorithms, Applied Mathematics, (2002), SIAM University of Manchester, Manchester, England · Zbl 1011.65010
[24] M.G. et al., GNU scientific library reference manual, 3rd Ed. ISBN:0954612078.
[25] Oste, R.; der Jeugt, J. V., Tridiagonal test matrices for eigenvalue computations: two-parameter extensions of the clement matrix, J. Comput. Appl. Math., 314, 30-39, (2017) · Zbl 1354.65075
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.