article

Free access

Sparsity structure and Gaussian elimination

Authors:

I. S. Duff,

A. M. Erisman,

C. W. Gear,

J. K. ReidAuthors Info & Claims

ACM SIGNUM Newsletter, Volume 23, Issue 2

Pages 2 - 8

https://doi.org/10.1145/47917.47918

Published: 01 April 1988 Publication History

PDF eReader

Abstract

In this paper we collate and discuss some results on the sparsity structure of a matrix. If a matrix is irreducible, Gaussian elimination yields an LU factorization in which L has at least one entry beneath the diagonal in every column except the last and U has at least one entry to the right of the diagonal in every row except the last. If this factorization is used to solve the equation Ax=b, the intermediate vector has an entry in its last component and the solution x is full. Furthermore, the inverse of A is full.Where the matrix is reducible, these results are applicable to the diagonal blocks of its block triangular form.

References

[1]

Duff, I. S. and Reid, J. K. (1978). "An implementation of Tarjan's algorithm for the block triangularization of a matrix". ACM Trans. Math. Soft. 4, pp. 137--147.

Digital Library

Google Scholar

[2]

Tarjan, R. E. (1972). "Depth-first search and linear graph algorithms". SIAM J. Comput. 1, pp. 146--160.

Digital Library

Google Scholar

[3]

Willoughby, R. A. (1975). "A characterization of matrix irreducibility". International Series of Numerical Mathematics 29. Birkhauser Verlag, pp. 131--143.

Google Scholar

[4]

Schneider, H. (1977). "The concepts of irreducibility and full indecomposability of a matrix". Linear Algebra and its Applications 18, pp. 139--162

Google Scholar

Cited By

View all

Örmecioğlu TAydoğdu İÖrmecioğlu H(2024)GPU-based parallel programming for FEM analysis in the optimization of steel framesJournal of Asian Architecture and Building Engineering10.1080/13467581.2024.2345310(1-22)Online publication date: 9-May-2024
https://doi.org/10.1080/13467581.2024.2345310
Li MWang HJimack P(2024)Generative Modeling of Sparse Approximate Inverse PreconditionersComputational Science – ICCS 202410.1007/978-3-031-63759-9_40(378-392)Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63759-9_40
Spišák MBartyzal RHoskovec APeska LTůma M(2023)Scalable Approximate NonSymmetric Autoencoder for Collaborative FilteringProceedings of the 17th ACM Conference on Recommender Systems10.1145/3604915.3608827(763-770)Online publication date: 14-Sep-2023
https://dl.acm.org/doi/10.1145/3604915.3608827
Show More Cited By

Index Terms

Sparsity structure and Gaussian elimination
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices

Recommendations

Gaussian elimination
Abstract
As the standard method for solving systems of linear equations, Gaussian elimination (GE) is one of the most important and ubiquitous numerical algorithms. However, its successful use relies on understanding its numerical stability properties and ...
Pivoting techniques for symmetric Gaussian elimination

In order to factorize an indefinite symmetric matrix G of the form G=LDL ^T where L is a trivially invertible matrix and D is a diagonal matrix, we introduce a new kind of pivoting operation. The algorithm suggested maintains the stability and ...
Symbolic and Exact Structure Prediction for Sparse Gaussian Elimination with Partial Pivoting

In this paper we consider two structure prediction problems of interest in Gaussian elimination with partial pivoting of sparse matrices. First, we consider the problem of determining the nonzero structure of the factors $L$ and $U$ during the ...

Comments

Information & Contributors

Information

Published In

ACM SIGNUM Newsletter Volume 23, Issue 2

April 1988

59 pages

ISSN:0163-5778

DOI:10.1145/47917

Editor:
P. W. Gaffney
Bergin Scientific Centre, Bergen, Norway

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1988

Published in SIGNUM Volume 23, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
360
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)5

Reflects downloads up to 22 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Örmecioğlu TAydoğdu İÖrmecioğlu H(2024)GPU-based parallel programming for FEM analysis in the optimization of steel framesJournal of Asian Architecture and Building Engineering10.1080/13467581.2024.2345310(1-22)Online publication date: 9-May-2024
https://doi.org/10.1080/13467581.2024.2345310
Li MWang HJimack P(2024)Generative Modeling of Sparse Approximate Inverse PreconditionersComputational Science – ICCS 202410.1007/978-3-031-63759-9_40(378-392)Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63759-9_40
Spišák MBartyzal RHoskovec APeska LTůma M(2023)Scalable Approximate NonSymmetric Autoencoder for Collaborative FilteringProceedings of the 17th ACM Conference on Recommender Systems10.1145/3604915.3608827(763-770)Online publication date: 14-Sep-2023
https://dl.acm.org/doi/10.1145/3604915.3608827
Scott JTůma MScott JTůma M(2023)Stability, Ill-Conditioning, and Symmetric Indefinite FactorizationsAlgorithms for Sparse Linear Systems10.1007/978-3-031-25820-6_7(113-134)Online publication date: 11-Jan-2023
https://doi.org/10.1007/978-3-031-25820-6_7
Davis TRajamanickam SSid-Lakhdar W(2016)A survey of direct methods for sparse linear systemsActa Numerica10.1017/S096249291600007625(383-566)Online publication date: 23-May-2016
https://doi.org/10.1017/S0962492916000076
Kriemann RLe Borne S(2015)$$\mathcal H$$H-FAINVComputing and Visualization in Science10.1007/s00791-015-0254-y17:3(135-150)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1007/s00791-015-0254-y
Bouchet LAmestoy PButtari ARouet FChauvin M(2013)Simultaneous analysis of large INTEGRAL/SPI11Based on observations with INTEGRAL, an ESA project with instruments and science data center funded by ESA member states (especially the PI countries: Denmark, France, Germany, Italy, Spain, and Switzerland), Czech Republic and Poland with participation of Russia and the USA. datasets: Optimizing the computation of the solution and its variance using sparse matrix algorithmsAstronomy and Computing10.1016/j.ascom.2013.03.0021(59-69)Online publication date: Feb-2013
https://doi.org/10.1016/j.ascom.2013.03.002
Kuzmin ALuisier MSchenk O(2013)Fast methods for computing selected elements of the green's function in massively parallel nanoelectronic device simulationsProceedings of the 19th international conference on Parallel Processing10.1007/978-3-642-40047-6_54(533-544)Online publication date: 26-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40047-6_54
Duff IUçar B(2012)Combinatorial Problems in Solving Linear SystemsCombinatorial Scientific Computing10.1201/b11644-3(21-68)Online publication date: 29-Mar-2012
https://doi.org/10.1201/b11644-3
Amestoy PDuff IL'Excellent JRobert YRouet FUçar B(2012)On Computing Inverse Entries of a Sparse Matrix in an Out-of-Core EnvironmentSIAM Journal on Scientific Computing10.1137/10079941134:4(A1975-A1999)Online publication date: Jan-2012
https://doi.org/10.1137/100799411
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Gaussian elimination

Pivoting techniques for symmetric Gaussian elimination

Symbolic and Exact Structure Prediction for Sparse Gaussian Elimination with Partial Pivoting

Comments

Information

Published In

Publisher

Publication History

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations