research-article

Quadratic-time certificates in linear algebra

Authors:

Erich L. Kaltofen,

Michael Nehring,

B. David SaundersAuthors Info & Claims

ISSAC '11: Proceedings of the 36th international symposium on Symbolic and algebraic computation

Pages 171 - 176

https://doi.org/10.1145/1993886.1993915

Published: 08 June 2011 Publication History

Abstract

We present certificates for the positive semidefiniteness of an n by n matrix A, whose entries are integers of binary length log ||A||, that can be verified in O(n^(2+µ) (log ||A||)^(1+µ) binary operations for any µ > 0. The question arises in Hilbert/Artin-based rational sum-of-squares certificates (proofs) for polynomial inequalities with rational coefficients. We allow certificates that are validated by Monte Carlo randomized algorithms, as in Rusins Freivalds's famous 1979 quadratic time certification for the matrix product. Our certificates occupy O(n^(3+µ) (log ||A||)^(1+µ) bits, from which the verfication algorithm randomly samples a quadratic amount.

In addition, we give certificates of the same space and randomized validation time complexity for the Frobenius form, which includes the characteristic and minimal polynomial. For determinant and rank we have certificates of essentially-quadratic binary space and time complexity via Storjohann's algorithms.

References

[1]

Eberly, W., Giesbrecht, M., and Villard, G. On computing the determinant and Smith form of an integer matrix. In Proc. 41st Annual Symp. Foundations of Comp. Sci. (Los Alamitos, California, 2000), IEEE Computer Society Press, pp. 675--685.

Digital Library

[2]

Freivalds, R. Fast probabilistic algorithms. In Mathematical Foundations of Computer Science 1979, Proceedings, 8th Symposium, Olomouc, Czechoslovakia, September 3-7, 1979 (1979), J. Becvár, Ed., Springer, pp. 57--69. Lecture Notes in Computer Science, vol. 74.

[3]

Giesbrecht, M., Lobo, A., and Saunders, B. D. Certifying inconsistency of sparse linear systems. In ISSAC 98 Proc. 1998 Internat. Symp. Symbolic Algebraic Comput. (New York, N. Y., 1998), O. Gloor, Ed., ACM Press, pp. 113--119.

Digital Library

[4]

Giesbrecht, M., and Storjohann, A. Computing rational forms of integer matrices. J. Symbolic Comput. 34, 3 (Sept. 2002), 157--172.

Digital Library

[5]

Goldstein, A. J., and Graham, R. L. A Hadamard-type bound on the coefficients of a determinant of polynomials. SIAM Rev. 16 (1974), 394--395.

Digital Library

[6]

Kaltofen, E., Krishnamoorthy, M. S., and Saunders, B. D. Fast parallel computation of Hermite and Smith forms of polynomial matrices. SIAM J. Alg. Discrete Math. 8 (1987), 683--690. http://www.math.ncsu.edu/~kaltofen/bibliography/87/KKS87.pdf

Digital Library

[7]

Kaltofen, E., Li, B., Yang, Z., and Zhi, L. Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars. In ISSAC 2008 (New York, N. Y., 2008), D. Jeffrey, Ed., ACM Press, pp. 155--163. http://www.math.ncsu.edu/~kaltofen/bibliography/08/KLYZ08.pdf EKbib/08/KLYZ08.pdf

Digital Library

[8]

Kaltofen, E., and Villard, G. On the complexity of computing determinants. Computational Complexity 13, 3-4 (2004), 91--130. http://www.math.ncsu.edu/~kaltofen/bibliography/04/KaVi04_2697263.pdf

Digital Library

[9]

Kaltofen, E. L., Li, B., Yang, Z., and Zhi, L. Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients, Jan. 2009. Accepted for publication in J. Symbolic Comput. http://www.math.ncsu.edu/~kaltofen/bibliography/09/KLYZ09.pdf

Digital Library

[10]

Kimbrel, T., and Sinha, R. K. A probabilistic algorithm for verifying matrix products using O(n<sup>2</sup>) time and log_2 n+O(1) random bits. Inf. Process. Lett. 45, 2 (1993), 107--110.

Digital Library

[11]

MacLane, S., and Birkhoff, G. Algebra, second edition. Macmillan, 1979.

[12]

May, J. P., Ed. ISSAC 2009 Proc. 2009 Internat. Symp. Symbolic Algebraic Comput. (New York, N. Y., 2009), ACM.

[13]

Rosser, J. B., and Schoenfeld, L. Approximate formulas of some functions of prime numbers. Illinois J. Math. 6 (1962), 64--94.

[14]

Saunders, B. D., and Youse, B. S. Large matrix, small rank. In May {12}, pp. 317--324.

[15]

Storjohann, A. The shifted number system for fast linear algebra on integer matrices. J. Complexity 21, 5 (2005), 609--650.

Digital Library

[16]

Storjohann, A. Integer matrix rank certification. In May {12}, pp. 333--340.

Cited By

Roche D(2024)Corrigimus, verificamus, vincimus: Ensuring algorithmic accuracy in an age of uncertaintyProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3672621(8-10)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3672621
Kaltofen E(2024)Encounters in Symbolic Computation: Ideas for the AgesProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3672619(1-7)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3672619
Hon WTsai MWang H(2023)Verifying the Product of Generalized Boolean Matrix Multiplication and Its Applications to Detect Small SubgraphsAlgorithms and Data Structures10.1007/978-3-031-38906-1_33(507-520)Online publication date: 28-Jul-2023
https://doi.org/10.1007/978-3-031-38906-1_33
Show More Cited By

Index Terms

Quadratic-time certificates in linear algebra
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

Essentially optimal interactive certificates in linear algebra
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

Certificates to a linear algebra computation are additional data structures for each output, which can be used by a---possibly randomized---verification algorithm that proves the correctness of each output. The certificates are essentially optimal if ...
The shifted number system for fast linear algebra on integer matrices
Festschrift for the 70th birthday of Arnold Schönhage

The shifted number system is presented: a method for detecting and avoiding error producing carries during approximate computations with truncated expansions of rational numbers. Using the shifted number system the high-order lifting and integrality ...
Parallel Output-Sensitive Algorithms for Combinatorial and Linear Algebra Problems

This paper gives output-sensitive parallel algorithms whose performance depends on the output size and are significantly more efficient tan previous algorithms for problems with sufficiently small output size. Inputs are n n matrices over a fixed ground ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '11: Proceedings of the 36th international symposium on Symbolic and algebraic computation

June 2011

372 pages

ISBN:9781450306751

DOI:10.1145/1993886

General Chair:
Éric Schost
The University of Western Ontario, Canada
,
Program Chair:
Ioannis Z. Emiris
University of Athens, Greece

Copyright © 2011 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: 08 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC '11

Sponsor:

SIGSAM

ISSAC '11: International Symposium on Symbolic and Algebraic Computation

June 8 - 11, 2011

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
92
Total Downloads

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

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Roche D(2024)Corrigimus, verificamus, vincimus: Ensuring algorithmic accuracy in an age of uncertaintyProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3672621(8-10)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3672621
Kaltofen E(2024)Encounters in Symbolic Computation: Ideas for the AgesProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3672619(1-7)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3672619
Hon WTsai MWang H(2023)Verifying the Product of Generalized Boolean Matrix Multiplication and Its Applications to Detect Small SubgraphsAlgorithms and Data Structures10.1007/978-3-031-38906-1_33(507-520)Online publication date: 28-Jul-2023
https://doi.org/10.1007/978-3-031-38906-1_33
Dumas JKaltofen ELucas DPernet C(2020)Elimination-based certificates for triangular equivalence and rank profilesJournal of Symbolic Computation10.1016/j.jsc.2019.07.01398:C(246-269)Online publication date: 1-May-2020
https://dl.acm.org/doi/10.1016/j.jsc.2019.07.013
Dumas Jvan der Hoeven JPernet CRoche DDavenport JWang DKauers MBradford R(2019)LU Factorization with ErrorsProceedings of the 2019 International Symposium on Symbolic and Algebraic Computation10.1145/3326229.3326244(131-138)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3326229.3326244
Dumas JPernet CKauers MOvchinnikov ASchost É(2018)Symmetric Indefinite Triangular Factorization Revealing the Rank Profile MatrixProceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3209019(151-158)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3208976.3209019
Roche DKauers MOvchinnikov ASchost É(2018)Error Correction in Fast Matrix Multiplication and InverseProceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3209001(343-350)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3208976.3209001
Giorgi PNeiger VKauers MOvchinnikov ASchost É(2018)Certification of Minimal Approximant BasesProceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3208991(167-174)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3208976.3208991
Dumas J(2018)Proof-of-Work Certificates that Can Be Efficiently Computed in the Cloud (Invited Talk)Developments in Language Theory10.1007/978-3-319-99639-4_1(1-17)Online publication date: 23-Aug-2018
https://doi.org/10.1007/978-3-319-99639-4_1
Mantzaflaris ASchost ETsigaridas EYap CEl Din M(2017)Sparse Rational Univariate RepresentationProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087653(301-308)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087653
Show More Cited By

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.

Figures

Tables

Media

View Table of Conten