Abstract
New algorithms are described and analysed for solving various problems associated with a large integer matrix: computing the Hermite form, computing a kernel basis, and solving a system of linear diophantine equations. The algorithms are space-efficient and for certain types of input matrices — for example, those arising during the computation of class groups and regulators — are faster than previous methods. Experiments with a prototype implementation support the running time analyses.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
H. Cohen and H. Lenstra, Jr. Heuristics on class groups of number fields. In Number Theory, Lecture notes in Math., volume 1068, pages 33–62. Springer-Verlag, New York, 1983.
J. D. Dixon. Exact solution of linear equations using p-adic expansions. Numer. Math., 40:137–141, 1982.
P. D. Domich, R. Kannan, and L. E. Trotter, Jr. Hermite normal form computation using modulo determinant arithmetic. Mathematics of Operations Research, 12(1):50–59, 1987.
J. L. Hafner and K. S. McCurley. A rigorous subexponential algorithm for computation of class groups. J. Amer. Math. Soc., 2:837–850, 1989.
C. S. Iliopoulos. Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix. SIAM Journal of Computing, 18(4):658–669, 1989.
H. Iwaniec. On the problem of Jacobsthal. Demonstratio Mathematica, 11(1):225–231, 1978.
M. J. Jacobson, Jr. Subexponential Class Group Computation in Quadratic Orders. PhD thesis, Technischen Universität Darmstadt, 1999.
F. Lübeck. On the computation of elementary divisors of integer matrices. Journal of Symbolic Computation, 2001. To appear.
T. Mulders and A. Storjohann. Diophantine linear system solving. In S. Dooley, editor, Proc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’ 99, pages 281–288. ACM Press, 1999.
T. Mulders and A. Storjohann. Rational solutions of singular linear systems. In C. Traverso, editor, Proc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’ 00, pages 242–249. ACM Press, 2000.
A. Storjohann. A solution to the extended gcd problem with applications. In W. W. Küchlin, editor, Proc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’ 97, pages 109–116. ACM Press, 1997.
A. Storjohann. Algorithms for Matrix Canonical Forms. PhD thesis, ETH-Swiss Federal Institute of Technology, 2000.
J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, 1999.
D. Wiedemann. Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theory, IT-32:54–62, 1986.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Giesbrecht, M., Jr. Jacobson, M., Storjohann, A. (2001). Algorithms for Large Integer Matrix Problems. In: Boztaş, S., Shparlinski, I.E. (eds) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC 2001. Lecture Notes in Computer Science, vol 2227. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45624-4_31
Download citation
DOI: https://doi.org/10.1007/3-540-45624-4_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42911-1
Online ISBN: 978-3-540-45624-7
eBook Packages: Springer Book Archive