Skip to main content
Springer Nature Link
Log in

Generalized elimination method and its applications to matrix factorizations

  • Original Research
  • Published:
Indian Journal of Pure and Applied Mathematics Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. 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.

    Article  MathSciNet  Google Scholar 

  2. B. Bylina and J. Bylina, The WZ factorization in MATLAB In 2014 Federated Conference on Computer Science and Information Systems (IEEE), (2014) 561-568.

  3. J. R. Bunch, Block methods for solving sparse linear systems, Sparse Matrix Computations, Academic Press, 1976, 39–58.

    Google Scholar 

  4. B. Codenotti, and F. Romani, A note on quadrant interlocking factorization. IMA journal of numerical analysis, 9(2) (1989) 139–143.

  5. 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.

    Article  MathSciNet  Google Scholar 

  6. 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.

  7. 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.

    Article  MathSciNet  Google Scholar 

  8. D.J. Evans and M. Hatzopoulos, A parallel linear system solver, International Journal of Computer Mathematics, 7(3) (1979) 227-238.

    Article  MathSciNet  Google Scholar 

  9. D.J. Evans, Implicit matrix elimination (IME) schemes, International Journal of Computer Mathematics, 48(3-4) (1993) 229-237.

    Article  Google Scholar 

  10. 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.

    Article  MathSciNet  Google Scholar 

  11. 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.

    Article  MathSciNet  Google Scholar 

  12. 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.

    Article  MathSciNet  Google Scholar 

  13. 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.

    Article  MathSciNet  Google Scholar 

  14. A. Galantai, The rank reduction procedure of Egerváry. Central European Journal of Operations Research, 18(1) (2010) 5.

    Article  MathSciNet  Google Scholar 

  15. K. A. Gallivan, R. J. Plemmons and A. H. Sameh, Parallel algorithms for dense linear algebra computations, SIAM Review, 32(1) (1990) 54-135.

    Article  MathSciNet  Google Scholar 

  16. 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.

    MathSciNet  Google Scholar 

  17. 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.

    Article  MathSciNet  Google Scholar 

  18. G. H. Golub and C. F. Van Loan, Matrix computation (4th edition), The johns hopkins university press, 2013.

  19. 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.

    Google Scholar 

  20. N. J. Higham, Accuracy and stability of numerical algorithms (2th edition), Society for industrial and applied mathematics, 2002.

  21. 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.

    Article  MathSciNet  Google Scholar 

  22. 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.

    Article  MathSciNet  Google Scholar 

  23. S.C.S. Rao, Existence and uniqueness of WZ factorization, Parallel Computing, 23(8) (1997) 1129-1139.

    Article  MathSciNet  Google Scholar 

  24. 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.

    Article  MathSciNet  Google Scholar 

  25. J. Shanehchi and D. J. Evans, New variants of the quadrant interlocking factorization (QIF) method, International Conference on Parallel Processing, (1981), 493-507.

  26. R. Schreiber, Block algorithms for parallel machines, Numerical Algorithms for Modern Parallel Computer Architectures, Springer, New York, 1988.

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Qom, Qom, Iran

    E. Golpar-Raboky

Authors
  1. E. Golpar-Raboky
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to E. Golpar-Raboky.

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s13226-024-00678-1

Keywords

Mathematics Subject Classification

Search

Navigation