×

Eigenvalue clustering of coefficient matrices in the iterative stride reductions for linear systems. (English) Zbl 1443.65047

Summary: Solvers for linear systems with tridiagonal coefficient matrices sometimes employ direct methods such as the Gauss elimination method or the cyclic reduction method. In each step of the cyclic reduction method, nonzero offdiagonal entries in the coefficient matrix move incrementally away from diagonal entries and eventually vanish. The steps of the cyclic reduction method are generalized as forms of the stride reduction method. For example, the 2-stride reduction method coincides with the 1st step of the cyclic reduction method which transforms tridiagonal linear systems into pentadiagonal systems. In this paper, we explain arbitrary-stride reduction for linear systems with coefficient matrices with three nonzero bands. We then show that arbitrary-stride reduction is equivalent to a combination of 2-stride reduction and row and column permutations. We thus clarify eigenvalue clustering of coefficient matrices in the step-by-step process of the stride reduction method. We also provide two examples verifying this property.

MSC:

65F10 Iterative numerical methods for linear systems
65F05 Direct numerical methods for linear systems and matrix inversion
15A06 Linear equations (linear algebraic aspects)
Full Text: DOI

References:

[1] Varga, R. S., Matrix Iterative Analysis (1962), Pren-tice-Hall · Zbl 0133.08602
[2] (Wilkinson, J. H.; Reinsch, C. H., Linear Algebra (1971), Springer-Verlag)
[3] Reinsch, C. H., Smoothing by spline functions, Numer. Math., 10, 177-183 (1967) · Zbl 0161.36203
[4] Evans, J. D., Cyclic and stride reduction methods for generalised tridiagonal matrices, Int. J. Comput. Math., 73, 487-492 (2000) · Zbl 0990.65039
[6] Buzbee, B. L.; Golub, G. H.; Nielson, C. W., On direct methods for solving Poisson’s equation, SIAM J. Numer. Anal., 7, 627-656 (1970) · Zbl 0217.52902
[7] Sweet, R. A., A generalized cyclic reduction algorithm, SIAM J. Numer. Anal., 11, 506-520 (1974) · Zbl 0253.65061
[8] Gallopoulos, E.; Saad, Y., A parallel block cyclic reduction algorithm for the fast solution of elliptic equations, (Lect. Note Computer Sci., vol. 297 (1988)), 563-575
[9] Seal, S. K.; Perumalla, K. S.; Hirshman, S. P., Revisiting parallel cyclic reduction and parallel prefix-based algorithms for block tridiagonal systems of equations, J. Parallel Distrib. Comput., 73, 273-280 (2013) · Zbl 1270.68386
[10] Golub, G. H.; Van Loan, C. F., Matrix Computations (2012), Johns Hopkins
[11] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM · Zbl 1002.65042
[12] Wang, T.; Iwasaki, M.; Nakamura, Y., On condition numbers in the cyclic reduction processes of a tridiagonal matrix, Int. J. Comput. Math., 87, 3079-3093 (2010) · Zbl 1213.65073
[13] Jia, J. T.; Sogabe, T.; El-Mikkawy, M. E.A., Inversion of \(k\)-tridiagonal matrices with Toeplitz structure, Comput. Math. Appl., 65, 116-125 (2013) · Zbl 1268.15002
[14] Sogabe, T.; El-Mikkawy, M. E.A., Fast block diagonalization of \(k\)-tridiagonal matrices, Appl. Math. Comput., 218, 2740-2743 (2011) · Zbl 1478.65015
[15] Žecová, M.; Terpák, J., Heat conduction modeling by using fractional-order derivatives, Appl. Math. Comput., 257, 365-373 (2015) · Zbl 1338.80012
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.