Abstract
An elimination method is a sequence of elementary row or column operations to divide a matrix into parts with partial zeroing of columns or rows of the matrix leading to a matrix factorization implicitly. We present a generalized elimination algorithm for solving real and Diophantine linear systems. The algorithm uses a zeroing process based on two index sets and provides a mechanism for constructing factorizations such as block LU factorization as well as the WZ and the ZW factorizations under a common framework. We also introduce the octant interlocking factorization method and present two new factorizations named as the ODS and the SDO factorizations. Necessary and sufficient conditions under which the generalized elimination method is carried out are proposed.
Similar content being viewed by others
References
B. Bylina and J. Bylina, The Parallel Tiled WZ Factorization Algorithm for Multicore Architectures, International Journal of Applied Mathematics and Computer Science, 29(2) (2019) 407–419.
B. Bylina and J. Bylina, The WZ factorization in MATLAB In 2014 Federated Conference on Computer Science and Information Systems (IEEE), (2014) 561-568.
J. R. Bunch, Block methods for solving sparse linear systems, Sparse Matrix Computations, Academic Press, 1976, 39–58.
B. Codenotti, and F. Romani, A note on quadrant interlocking factorization. IMA journal of numerical analysis, 9(2) (1989) 139–143.
J. W. Demmel, N. J. Higham and R. S. Schreiber, Stability of Block LU Factorization, Numerical Linear Algebra with Applications, 2(2) (1995) 173–190.
J. W. Demmel, N. J. Higham and R. S. Schreiber, Stability of block algorithms with fast level-3 BLAS, ACM Transaction on Mathematical Software (TOMS), 18(3) (1992) 274-291., Numerical Linear Algebra with Applications, 2(2) (1995) 173–190.
C. Echeverria,J. Liesen and R. Nabben, Block diagonal dominance of matrices revisited: bounds for the norms of inverses and eigenvalue inclusion sets. Linear Algebra and its Applications, 553 (2018) 365–383.
D.J. Evans and M. Hatzopoulos, A parallel linear system solver, International Journal of Computer Mathematics, 7(3) (1979) 227-238.
D.J. Evans, Implicit matrix elimination (IME) schemes, International Journal of Computer Mathematics, 48(3-4) (1993) 229-237.
D.J. Evans and A. Hadjidimos, A modification of the quadrant interlocking factorization parallel method, International Journal of Computer Mathematics, 8(2) (1980) 149-166.
D.J. Evans, A. Hadjidimos and D. Noutsos, Parallel solution of linear systems by quadrant interlocking factorization methods, Computer Methods in Applied Mechanics and Engineering, 29(1) (1981a) 97-107.
D.J. Evans, A. Hadjidimos and D. Noutsos, The parallel solution of banded linear equation by the new quadrant interlocking factorization (QIF) method, International Journal of Computer Mathematics, 9(2) (1981b) 151-161.
D.J. Evans and A. Hadjidimos, Parallel solution to certain banded, symmetric and centro-symmetric systems by using the quadrant interlocking factorization method, Mathematics and Computers in Simulation, 23(2) (1981) 180-187.
A. Galantai, The rank reduction procedure of Egerváry. Central European Journal of Operations Research, 18(1) (2010) 5.
K. A. Gallivan, R. J. Plemmons and A. H. Sameh, Parallel algorithms for dense linear algebra computations, SIAM Review, 32(1) (1990) 54-135.
E. Golpar-Raboky and N. Mahdavi-Amiri, WZ factorization via Abaffy-Broyden-Spedicato algorithms, Bulletin of the Iranian Mathematical Society, 40(2) (2014) 399-411.
E. Golpar-Raboky and N. Mahdavi-Amiri, A new interpretation of the WZ factorization using block scaled ABS algorithms, Statistics, Optimization and Information Computing, 2(3) (2014) 243-256.
G. H. Golub and C. F. Van Loan, Matrix computation (4th edition), The johns hopkins university press, 2013.
A. Hadjidimos and D. Noutsos, Special similarity transformations in connection with the quadrant interlocking factorization techniques, Bulletin of the Greek Mathematical Society, 22(22) (1981) 44-66.
N. J. Higham, Accuracy and stability of numerical algorithms (2th edition), Society for industrial and applied mathematics, 2002.
N. Mahdavi-Amiri, E. Golpar-Raboky, Real and integer Wedderburn rank reduction formulas for matrix decompositions, Optimization Methods and Software, 30(4) (2015) 864-879.
R. M. M. Mattheij. Stability of block LU-decompositions of matrices arising from BVP. SIAM Journal on Algebraic Discrete Mathematics, 5(3) (1984) 314-331.
S.C.S. Rao, Existence and uniqueness of WZ factorization, Parallel Computing, 23(8) (1997) 1129-1139.
S.C.S. Rao and R. Kamra, A hybrid parallel algorithm for large sparse linear systems, Numerical Linear Algebra with Applications, 25(6) (2018) e2210.
J. Shanehchi and D. J. Evans, New variants of the quadrant interlocking factorization (QIF) method, International Conference on Parallel Processing, (1981), 493-507.
R. Schreiber, Block algorithms for parallel machines, Numerical Algorithms for Modern Parallel Computer Architectures, Springer, New York, 1988.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Rahul Roy.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Golpar-Raboky, E. Generalized elimination method and its applications to matrix factorizations. Indian J Pure Appl Math (2024). https://doi.org/10.1007/s13226-024-00678-1
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s13226-024-00678-1
Keywords
- Generalized elimination method
- Matrix factorization
- Quadrant interlocking factorization
- Octant interlocking factorization