×

The shifted number system for fast linear algebra on integer matrices. (English) Zbl 1101.68045

Summary: 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 certification techniques of Storjohann (2003) for polynomial matrices are extended to the integer case. Las Vegas reductions to integer matrix multiplication are given for some problems involving integer matrices: the determinant and a solution of a linear system can be computed with about the same number of bit operations as required to multiply together two matrices having the same dimension and size of entries as the input matrix. The algorithms are space efficient.

MSC:

68Q25 Analysis of algorithms and problem complexity
65Y20 Complexity and performance of numerical algorithms
65F99 Numerical linear algebra
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abbott, J.; Bronstein, M.; Mulders, T., Fast deterministic computation of determinants of dense matrices, (Dooley, S., Proceedings of the International Symposium on Symbolic and Algebraic Computation: ISSAC ’99 (1999), ACM Press: ACM Press New York), 197-204
[2] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0207.01701
[3] Brönnimann, H.; Yvinec, M., Efficient exact evaluation of signs of determinants, Algorithmica, 21, 21-56 (2000) · Zbl 0947.65053
[4] Bürgisser, P.; Clausen, M.; Shokrollahi, M. A., Algebraic Complexity Theory, Grundlehren der mathematischen Wissenschaften, vol. 315 (1996), Springer: Springer Berlin
[5] Z. Chen, A BLAS based C library for exact linear algebra on integer matrices, Master’s thesis, School of Computer Science, University of Waterloo, 2005.; Z. Chen, A BLAS based C library for exact linear algebra on integer matrices, Master’s thesis, School of Computer Science, University of Waterloo, 2005.
[6] Chen, Z.; Storjohann, A., A BLAS based C library for exact linear algebra on integer matrices, (Kauers, M., Proceedings of the International Symposium on Symbolic and Algebraic Computation: ISSAC ’05 (2005), ACM Press: ACM Press New York) · Zbl 1360.65086
[7] Clarkson, K. L., Safe and efficient determinant evaluation, (Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, Los Alamitos, CA (1992), IEEE Computer Society Press: IEEE Computer Society Press Silver Spring, MO), 387-395 · Zbl 0927.68040
[8] Coppersmith, D., Rectangular matrix multiplication revisited, J. Complexity, 13, 42-49 (1997) · Zbl 0872.68052
[9] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. Symbolic Computation, 9, 251-280 (1990) · Zbl 0702.65046
[10] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT Press, McGraw-Hill: MIT Press, McGraw-Hill Cambridge, MA, New York · Zbl 1047.68161
[11] Dixon, J. D., Exact solution of linear equations using p-adic expansions, Numer. Math., 40, 137-141 (1982) · Zbl 0492.65016
[12] W. Eberly, Asymptotically efficient algorithms for the Frobenius form, Technical Report, Department of Computer Science, University of Calgary, 2000.; W. Eberly, Asymptotically efficient algorithms for the Frobenius form, Technical Report, Department of Computer Science, University of Calgary, 2000.
[13] W. Eberly, M. Giesbrecht, G. Villard, Computing the determinant and Smith form of an integer matrix, in: Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, 2000, pp. 675-685.; W. Eberly, M. Giesbrecht, G. Villard, Computing the determinant and Smith form of an integer matrix, in: Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, 2000, pp. 675-685.
[14] I.Z. Emiris, V.Y. Pan, Improved algorithms for computing determinants and resultants, J. Complexity 21 (1) (2005) 43-71.; I.Z. Emiris, V.Y. Pan, Improved algorithms for computing determinants and resultants, J. Complexity 21 (1) (2005) 43-71. · Zbl 1101.68981
[15] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1055.68168
[16] Geddes, K. O.; Czapor, S. R.; Labahn, G., Algorithms for Computer Algebra (1992), Kluwer: Kluwer Boston, MA · Zbl 0805.68072
[17] M. Giesbrecht, Nearly optimal algorithms for canonical matrix forms, Ph.D. thesis, University of Toronto, 1993.; M. Giesbrecht, Nearly optimal algorithms for canonical matrix forms, Ph.D. thesis, University of Toronto, 1993. · Zbl 0839.65043
[18] Giesbrecht, M., Nearly optimal algorithms for canonical matrix forms, SIAM J. Comput., 24, 948-969 (1995) · Zbl 0839.65043
[19] Giesbrecht, M., Fast computation of the Smith form of a sparse integer matrix, Comput. Complexity, 10, 1, 41-69 (2001) · Zbl 0992.65039
[20] T. Granlund, The GNU multiple precision arithmetic library, 2004, Edition 4.1.4. http://www.swox.com/gmp; T. Granlund, The GNU multiple precision arithmetic library, 2004, Edition 4.1.4. http://www.swox.com/gmp
[21] Hafner, J. L.; McCurley, K. S., Asymptotically fast triangularization of matrices over rings, SIAM J. Comput., 20, 6, 1068-1083 (1991) · Zbl 0738.68050
[22] Ibarra, O.; Moran, S.; Hui, R., A generalization of the fast LUP matrix decomposition algorithm and applications, J. Algorithms, 3, 45-56 (1982) · Zbl 0492.65024
[23] Kaltofen, E., On computing determinants of matrices without divisions, (Wang, P. S., Proceedings of the International Symposium on Symbolic and Algebraic Computation: ISSAC ’92 (1992), ACM Press: ACM Press New York), 342-349 · Zbl 0978.65502
[24] Kaltofen, E., An output-sensitive variant of the baby steps/giant steps determinant algorithm, (Mora, T., Proceedings of the International Symposium on Symbolic and Algebraic Computation: ISSAC ’02 (2002), ACM Press: ACM Press New York), 138-144 · Zbl 1072.68675
[25] Kaltofen, E.; Krishnamoorthy, M. S.; Saunders, B. D., Parallel algorithms for matrix normal forms, Linear Algebra Appl., 136, 189-208 (1990) · Zbl 0727.65031
[26] Kaltofen, E.; Villard, G., Computing the sign or the value of the determinant of an integer matrix, a complexity survey, J. Comput. Appl. Math., 162, 1, 133-146 (2004), Special issue: Proceedings of the International Conference on Linear Algebra and Arithmetic 2001, Rabat, Morocco, 28-31 May 2001, S. El Hajji, N. Revol, P. Van Dooren (guest eds.) · Zbl 1037.65044
[27] Kaltofen, E.; Villard, G., On the complexity of computing determinants, Comput. Complexity, 13, 3-4, 91-130 (2004) · Zbl 1061.68185
[28] Knuth, D. E., The Art of Computer Programming, vol. 2, Seminumerical Algorithms (1981), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0477.65002
[29] Krandick, W.; Johnson, J., Efficient multiprecision floating point multiplication with optimal directional rounding, (11th IEEE Symposium on Computer Arithmetic (1993), IEEE Computer Society Press: IEEE Computer Society Press Silver Spring, MD), 228-233
[30] R.T. Moenck, J.H. Carter, Approximate algorithms to derive exact solutions to systems of linear equations, in: Proceedings EUROSAM ’79, Lecture Notes in Compute Science, vol. 72, Springer, Berlin, Heidelberg, New York, 1979, pp. 65-72.; R.T. Moenck, J.H. Carter, Approximate algorithms to derive exact solutions to systems of linear equations, in: Proceedings EUROSAM ’79, Lecture Notes in Compute Science, vol. 72, Springer, Berlin, Heidelberg, New York, 1979, pp. 65-72. · Zbl 0435.65023
[31] Mulders, T.; Storjohann, A., Certified dense linear system solving, J. Symbolic Comput., 37, 4, 485-510 (2004) · Zbl 1137.11361
[32] Newman, M., Integral Matrices (1972), Academic Press: Academic Press New York · Zbl 0254.15009
[33] Pan, V. Y., Computing the determinant and the characteristic polynomial of a matrix via solving linear systems of equations, Inf. Proc. Lett., 28, 71-75 (1988) · Zbl 0662.65039
[34] Pan, V. Y., Randomized acceleration of fundamental matrix computations, (Proceedings STACS 2002, vol. 2285 (2002), Springer: Springer Heidelberg, Germany), 215-226 · Zbl 1054.68830
[35] Pan, V. Y.; Wang, X., On rational number reconstruction and approximation, SIAM J. Comput., 33, 2, 502-503 (2004) · Zbl 1101.68997
[36] Rosser, J. B.; Schoenfeld, L., Approximate formulas for some functions of prime numbers, Ill. J. Math., 6, 64-94 (1962) · Zbl 0122.05001
[37] Saunders, D.; Storjohann, A.; Villard, G., Matrix rank certification, Electronic J. Linear Algebra, 11, 16-23 (2004) · Zbl 1038.65038
[38] Schönhage, A., Schnelle Berechnung von Kettenbruchentwicklungen, Acta Inform., 1, 139-144 (1971) · Zbl 0223.68008
[39] Schönhage, A.; Strassen, V., Schnelle Multiplikation grosser Zahlen, Computing, 7, 281-292 (1971) · Zbl 0223.68007
[40] Storjohann, A., Near optimal algorithms for computing Smith normal forms of integer matrices, (Lakshman, Y. N., Proceedings of the International Symposium on Symbolic and Algebraic Computation: ISSAC ’96 (1996), ACM Press: ACM Press New York), 267-274 · Zbl 0914.65043
[41] A. Storjohann, Algorithms for Matrix Canonical Forms, Ph.D. Thesis, Swiss Federal Institute of Technology, ETH-Zurich, 2000.; A. Storjohann, Algorithms for Matrix Canonical Forms, Ph.D. Thesis, Swiss Federal Institute of Technology, ETH-Zurich, 2000.
[42] Storjohann, A., High-order lifting, extended abstract, (Mora, T., Proceedings of the International Symposium on Symbolic and Algebraic Computation; ISSAC ’02 (2002), ACM Press: ACM Press New York), 246-254 · Zbl 1072.68698
[43] Storjohann, A., High-order lifting and integrality certification, J. Symbolic Comput., 36, 3-4, 613-648 (2003), Extended abstract in [42] · Zbl 1059.15020
[44] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 354-356 (1969) · Zbl 0185.40101
[45] Whaley, R. C.; Petitet, A.; Dongarra, J. J., Automated empirical optimization of software and the ATLAS project, Parallel Comput., 27, 1-2 (2001) · Zbl 0971.68033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.