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

research-article

Deterministic unimodularity certification

Authors:

Colton Pauderis,

Arne StorjohannAuthors Info & Claims

ISSAC '12: Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation

Pages 281 - 288

https://doi.org/10.1145/2442829.2442870

Published: 22 July 2012 Publication History

Abstract

The asymptotically fastest algorithms for many linear algebra problems on integer matrices, including solving a system of linear equations and computing the determinant, use high-order lifting. Currently, high-order lifting requires the use of a randomized shifted number system to detect and avoid error-producing carries. By interleaving quadratic and linear lifting, we devise a new algorithm for high-order lifting that allows us to work in the usual symmetric range modulo p, thus avoiding randomization. As an application, we give a deterministic algorithm to assay if an n x n integer matrix A is unimodular. The cost of the algorithm is O((log n)n^ω M(log n + log||A||)) bit operations, where ||A|| denotes the largest entry in absolute value, and M(t) is the cost of multiplying two integers bounded in bit length by t.

References

[1]

J. Berthomieu and R. Lebreton. Relaxed p-adic Hensel lifting for algebraic systems. In Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC'12. ACM Press, New York, 2012.

Digital Library

[2]

D. Bini and V. Y. Pan. Polynomial and Matrix Computations, Vol 1: Fundamental Algorithms. Birkhauser, Boston, 1994.

Digital Library

[3]

Z. Chen and A. Storjohann. A BLAS based C library for exact linear algebra on integer matrices. In M. Kauers, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC'05, pages 92--99. ACM Press, New York, 2005.

Digital Library

[4]

J. D. Dixon. Exact solution of linear equations using p-adic expansions. Numer. Math., 40:137--141, 1982.

Digital Library

[5]

J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, 2nd edition, 2003.

Digital Library

[6]

P. Giorgi. Arithmetic and algorithmic in exact linear algebra for the LinBox library. PhD thesis, École normale supérieure de Lyon, LIP, Lyon, France, December 2004.

[7]

T. Granlund and the GMP development team. Gnu mp: The GNU multiple precision arithmetic library, 2011. Edition 5.0.2. http://gmplib.org.

[8]

S. Gupta, S. Sarkar, A. Storjohann, and J. Valeriote. Triangular x-basis decompositions and derandomization of linear algebra algorithms over K{x}. Journal of Symbolic Computation, October 2011. Festschrift for the 60th Birthday of Joachim von zur Gathen. Accepted for publication.

Digital Library

[9]

J. L. Hafner and K. S. McCurley. Asymptotically fast triangularization of matrices over rings. SIAM Journal of Computing, 20(6):1068--1083, Dec. 1991.

Digital Library

[10]

E. Kaltofen. An output-sensitive variant of the baby steps/giant steps determinant algorithm. In T. Mora, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC'02, pages 138--144. ACM Press, New York, 2002.

Digital Library

[11]

E. Kaltofen and G. Villard. On the complexity of computing determinants. Computational Complexity, 13(3-4):91--130, 2004.

Digital Library

[12]

C. Pernet and W. Stein. Fast computation of Hermite normal forms of integer matrices. Journal of Number Theory, 130(7), 2010.

[13]

B. D. Saunders, D. H. Wood, and B. Youse. Numeric-symbolic exact rational linear system solver. In A. Leykin, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC'11, pages 305--312. ACM Press, New York, 2011.

Digital Library

[14]

D. Saunders and Z. Wan. Smith normal form of dense integer matrices, fast algorithms into practice. In J. Gutierrez, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC'04, pages 274--281. ACM Press, New York, 2004.

Digital Library

[15]

P. P. Shenoy and R. Kumaresan. Fast base extension using a redundant modulus in RNS. IEEE Trans. Comput., 38(2):292--297, Feb. 1989.

Digital Library

[16]

A. Storjohann. The shifted number system for fast linear algebra on integer matrices. Journal of Complexity, 21(4):609--650, 2005. Festschrift for the 70th Birthday of Arnold Schönhage.

Digital Library

[17]

A. Storjohann. Integer matrix rank certification. In J. P. May, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC'09, pages 333--340. ACM Press, New York, 2009.

Digital Library

[18]

R. C. Whaley, A. Petitet, and J. J. Dongarra. Automated empirical optimization of software and the ATLAS project. Parallel Computing, 27(1-2), 2001.

Cited By

Abbott JFieker C(2024)Computing the Determinant of a Dense Matrix over $${\mathbb Z}$$Mathematical Software – ICMS 202410.1007/978-3-031-64529-7_3(29-35)Online publication date: 17-Jul-2024
https://doi.org/10.1007/978-3-031-64529-7_3
Birmpilis SLabahn GStorjohann A(2023)A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrixJournal of Symbolic Computation10.1016/j.jsc.2022.09.002116:C(146-182)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.jsc.2022.09.002
Birmpilis SLabahn GStorjohann AEmiris IZhi LMantzaflaris A(2020)A Las Vegas algorithm for computing the smith form of a nonsingular integer matrixProceedings of the 45th International Symposium on Symbolic and Algebraic Computation10.1145/3373207.3404022(38-45)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.1145/3373207.3404022
Show More Cited By

Index Terms

Deterministic unimodularity certification

Recommendations

Integer matrix rank certification
ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation

Let M = [A B/C D] be a 2n x 2n integer matrix with the principal block A square and nonsingular. An algorithm is presented to determine if the Schur complement D--CA^--1 B is equal to the zero matrix in O~(n^ω log ||M||) bit operations. Here, ω is the ...
On the complexity of inverting integer and polynomial matrices

An algorithm is presented that probabilistically computes the exact inverse of a nonsingular n n integer matrix A using $${({n^3(\log||A||+\log \kappa(A)))}^{1+o(1)}}$$(n3(log||A||+log (A)))1+o(1) bit operations. Here, $${||A||= \max_{ij}|A_{ij}|}$$||A||...
On the complexity of computing determinants

We present new baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems. Our algorithms compute the determinant, characteristic polynomial, Frobenius normal form and Smith normal form of a dense n n matrix A ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '12: Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation

July 2012

390 pages

ISBN:9781450312691

DOI:10.1145/2442829

General Chair:
Joris van der Hoeven
École Polytechnique, France
,
Program Chair:
Mark van Hoeij
Florida State U.

Copyright © 2012 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

Grenoble University: Grenoble University
INRIA: Institut Natl de Recherche en Info et en Automatique

In-Cooperation

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC'12

Sponsor:

Grenoble University
INRIA

ISSAC'12: International Symposium on Symbolic and Algebraic Computation

July 22 - 25, 2012

Grenoble, France

Acceptance Rates

ISSAC '12 Paper Acceptance Rate 46 of 86 submissions, 53%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
105
Total Downloads

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

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Abbott JFieker C(2024)Computing the Determinant of a Dense Matrix over $${\mathbb Z}$$Mathematical Software – ICMS 202410.1007/978-3-031-64529-7_3(29-35)Online publication date: 17-Jul-2024
https://doi.org/10.1007/978-3-031-64529-7_3
Birmpilis SLabahn GStorjohann A(2023)A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrixJournal of Symbolic Computation10.1016/j.jsc.2022.09.002116:C(146-182)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.jsc.2022.09.002
Birmpilis SLabahn GStorjohann AEmiris IZhi LMantzaflaris A(2020)A Las Vegas algorithm for computing the smith form of a nonsingular integer matrixProceedings of the 45th International Symposium on Symbolic and Algebraic Computation10.1145/3373207.3404022(38-45)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.1145/3373207.3404022
Birmpilis SLabahn GStorjohann ADavenport JWang DKauers MBradford R(2019)Deterministic Reduction of Integer Nonsingular Linear System Solving to Matrix MultiplicationProceedings of the 2019 International Symposium on Symbolic and Algebraic Computation10.1145/3326229.3326263(58-65)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3326229.3326263
Pauderis CStorjohann AMonagan MCooperman GGiesbrecht M(2013)Computing the invariant structure of integer matricesProceedings of the 38th International Symposium on Symbolic and Algebraic Computation10.1145/2465506.2465955(307-314)Online publication date: 26-Jun-2013
https://dl.acm.org/doi/10.1145/2465506.2465955

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