More Web Proxy on the site http://driver.im/

research-article

Matrices with Two Nonzero Entries per Row

Author:

B. David SaundersAuthors Info & Claims

ISSAC '15: Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation

Pages 323 - 330

https://doi.org/10.1145/2755996.2756679

Published: 24 June 2015 Publication History

Abstract

Matrices with two nonzero entries per row (or per column) occur in many contexts. For example, edge-vertex incidence matrices of graphs have this form. Also, the boundary matrix for the highest dimensional simplices in a simplicial complex sometimes has this form as well. In particular, the homology of a triangulation of a 2 dimensional non-self-intersecting surface is obtained from the Smith forms of 2 two-per-row matrices (the edge-vertex and triangle-edge boundary matrices).

For an n by n matrix having just two nonzero entries per row, we show that rank, determinant, LU decomposition, and linear system solution can all be done in O(n) arithmetic operations (algebraic complexity). In the LU decomposition, U is bidiagonal and L, generally dense, is represented as a blackbox occupying O(n) space and such that matrix vector product with L and with its inverse can both be performed in O(n) arithmetic operations.

If the nonzero entries are restricted to one and minus one then rank, LU decomposition, and Smith normal form can be computed in essentially O(n) bit operations (ignoring log factors). In this limited situation, Smith form is meaningfully defined over any ring. Determinant and linear system solution can each be performed with O(n) additions and negations in the entry ring.

For integer two-per-row matrices with the nonzeros not limited to one and minus one, the methods here can be combined with standard techniques for algorithms of bit complexity greater than O(n) but less than the complexity for general matrices.

References

[1]

L. Chen, W. Eberly, E. Kaltofen, W. J. Turner, B. D. Saunders, and G. Villard. Efficient matrix preconditioners for black box linear algebra. Linear Algebra and Applications, 343--344:119--146, 2002.

[2]

R. Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, 2005.

[3]

J. D. Dixon. Exact solution of linear equations using p-adic expansion. Numer. Math., pages 137--141, 1982.

Digital Library

[4]

J-G. Dumas, B. D. Saunders, and G. Villard. Integer Smith form via the valence: Experience with large sparse matrices from homology. In ISSAC 00 Proc. 2000 Internat. Symp. Symbolic Algebraic Comput., pages 95--105. ACM Press, 2000.

Digital Library

[5]

Jean-Guillaume Dumas, Clément Pernet, and Ziad Sultan. Simultaneous computation of the row and column rank profiles. In Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC '13, pages 181--188, New York, NY, USA, 2013. ACM.

Digital Library

[6]

Jean-Guillaume Dumas, B. David Saunders, and Gilles Villard. On efficient sparse integer matrix Smith normal form computations. Journal of Symbolic Computation, 32:71--99, 2001.

Digital Library

[7]

W. Eberly, M. Giesbrecht, and G. Villard. On computing the determinant and Smith form of an integer matrix. 41st IEEE Symposium on Foundations of Computer Science, pages 675--687, 2000.

Digital Library

[8]

Mustafa ElSheik, Mark Giesbrecht, Andrew Novocin, and B. D. Saunders. Fast computation for Smith forms of sparse matrices over local rings. In Proc. 2012 Internat. Symp. Symbolic Algebraic Comput. ISSAC'12, pages 146--153. ACM Press, 2012.

Digital Library

[9]

F. R. Gantmacher. The Theory of Matrices. Chelsea, New York, NY, 1959.

[10]

Mark Giesbrecht. Probabilistic computation of the smith normal form of a sparse integer matrix. In Proceedings of the Second International Symposium on Algorithmic Number Theory, ANTS-II, pages 173--186, London, UK, UK, 1996. Springer-Verlag.

Digital Library

[11]

Allen Hatcher. Algebraic Topology. Cambridge University Press, Cambridge, UK, 2002.

[12]

Claude-Pierre Jeannerod, Clément Pernet, and Arne Storjohann. Rank-profile revealing gaussian elimination and the CUP matrix decomposition. Journal of Symbolic Computation, 56(0):46--68, 2013.

[13]

E. Kaltofen and B. D. Saunders. On Wiedemann's method of solving sparse linear systems. In H. F. Mattson, T. Mora, and T. R. N. Rao, editors, Proc. AAECC-9, volume 539 of Lect. Notes Comput. Sci., pages 29--38, Heidelberg, Germany, 1991. Springer Verlag.

Digital Library

[14]

Victor Y. Pan. Structured Matrices and Polynomials: Unified Superfast Algorithms. Springer-Verlag New York, Inc., New York, NY, USA, 2001.

Digital Library

[15]

B. D. Saunders and Z. Wan. Smith normal form of dense integer matrices, fast algorithms into practice. In ISSAC 04 Proc. 2004 Internat. Symp. Symbolic Algebraic Comput., pages 274--281. ACM Press, 2004.

Digital Library

[16]

D. Wiedemann. Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theory, it-32:54--62, 1986.

Digital Library

Cited By

Todd PAley D(2023)A program to create new geometry proof problemsAnnals of Mathematics and Artificial Intelligence10.1007/s10472-023-09854-191:6(779-795)Online publication date: 16-May-2023
https://dl.acm.org/doi/10.1007/s10472-023-09854-1
Todd P(2023)Automated discovery of angle theoremsAnnals of Mathematics and Artificial Intelligence10.1007/s10472-023-09841-691:6(753-778)Online publication date: 9-May-2023
https://dl.acm.org/doi/10.1007/s10472-023-09841-6
Bouillaguet CDelaplace C(2016)Sparse Gaussian Elimination Modulo p: An UpdateComputer Algebra in Scientific Computing10.1007/978-3-319-45641-6_8(101-116)Online publication date: 9-Sep-2016
https://doi.org/10.1007/978-3-319-45641-6_8

Index Terms

Matrices with Two Nonzero Entries per Row
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

On General Row Merging Schemes for Sparse Givens Transformations

This paper introduces general row merging schemes for the $QR$ decomposition of sparse matrices by Givens rotations. They can be viewed as a generalization of row rotations to submatrix rotations (or merging) in the recent method by George and Heath [12]...
Scaling Matrices to Prescribed Row and Column Maxima

A nonnegative symmetric matrix $B$ has row maxima prescribed by a given vector $r$, if for each index $i$, the maximum entry in the $i$th row of $B$ equals $r_i$. This paper presents necessary and sufficient conditions so that for a given nonnegative ...
A new preconditioner for indefinite and asymmetric matrices

We present a novel preconditioner for numerical solutions of large sparse linear systems with indefinite and asymmetric matrices. This new preconditioner named as product preconditioner(PS) is constructed by two fairly simple preconditioners. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '15: Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation

June 2015

374 pages

ISBN:9781450334358

DOI:10.1145/2755996

Conference Chair:
Daniel Robertz
Plymouth University, United Kingdom
,
General Chair:
Steve Linton
University of St Andrews, United Kingdom
,
Program Chair:
Kazuhiro Yokoyama
Rikkyo University, Japan

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC'15

Sponsor:

SIGSAM

ISSAC'15: International Symposium on Symbolic and Algebraic Computation

July 6 - 9, 2015

Bath, United Kingdom

Acceptance Rates

ISSAC '15 Paper Acceptance Rate 43 of 71 submissions, 61%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
166
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Todd PAley D(2023)A program to create new geometry proof problemsAnnals of Mathematics and Artificial Intelligence10.1007/s10472-023-09854-191:6(779-795)Online publication date: 16-May-2023
https://dl.acm.org/doi/10.1007/s10472-023-09854-1
Todd P(2023)Automated discovery of angle theoremsAnnals of Mathematics and Artificial Intelligence10.1007/s10472-023-09841-691:6(753-778)Online publication date: 9-May-2023
https://dl.acm.org/doi/10.1007/s10472-023-09841-6
Bouillaguet CDelaplace C(2016)Sparse Gaussian Elimination Modulo p: An UpdateComputer Algebra in Scientific Computing10.1007/978-3-319-45641-6_8(101-116)Online publication date: 9-Sep-2016
https://doi.org/10.1007/978-3-319-45641-6_8

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents