skip to main content
10.1145/1278177.1278186acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
Article

Parallel computation of the rank of large sparse matrices from algebraic K-theory

Published: 27 July 2007 Publication History

Abstract

This paper deals with the computation of the rank and some integer Smith forms of a series of sparse matrices arising in algebraic K-theory. The number of non zero entries in the considered matrices ranges from 8 to 37 millions. The largest rank computation took more than 35 days on 50 processors. We report on the actual algorithms we used to build the matrices, their link to the motivic cohomology and the linear algebra and parallelizations required to perform such huge computations. In particular, these results are part of the first computation of the cohomology of the linear group GL 7(Z).

References

[1]
J. Abbott, M. Bronstein, and T. Mulders. Fast deterministic computation of determinants of dense matrices. In S. Dooley, editor, Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, Vancouver, Canada, pages 197--204. ACM Press, New York, July 1999.
[2]
B. Beckermann and G. Labahn. A uniform approach for the fast computation of matrix-type Padé approximants.SIAM Journal on Matrix Analysis and Applications, 15(3): 804--823, 1994.
[3]
A. Bostan and E. Schost. Polynomial evaluation and interpolation on special sets of points. J. Complex., 21(4): 420--446, 2005.
[4]
K.S. Brown. Cohomology of groups.Graduate Texts in Mathematics,87.New York-Heidelberg-Berlin: Springer-Verlag. X, 306 p., 4 figs. DM 74.00 $ 29--60, 1982.
[5]
D.G. Cantor and E. Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Inf., 28(7): 693--701, 1991.
[6]
D. Coppersmith. Solving homogeneous linear equations over GF {2} via block Wiedemann algorithm. Mathematics of Computation, 62(205): 333--350, Jan. 1994.
[7]
J. D. Dixon. Exact solution of linear equations using p-adic expansions. Numerische Mathematik, 40(1):137--141, Feb. 1982.
[8]
J.-G. Dumas, editor. ISSAC '2006. Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, Santander, Spain. ACM Press, New York, July 2006.
[9]
J.-G. Dumas, B. D. Saunders, and G. Villard. On efficient sparse integer matrix Smith normal form computations. Journal of Symbolic Computations, 32(1/2): 71--99, jul-aug 2001.
[10]
J.-G. Dumas and G. Villard. Computing the rank of sparse matrices over finite fields. In V. G. Ganzha, E. W. Mayr, and E. V. Vorozhtsov, editors, Proceedings of the fifth International Workshop on Computer Algebra in Scientific Computing, Yalta, Ukraine, pages 47--62. Technische Universität München, Germany, Sept.2002.
[11]
W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann, and G. Villard. Solving sparse rational linear systems. In Dumas {8}, pages 63--70.
[12]
W. Eberly,M. Giesbrecht,and G. Villard. On computing the determinant and Smith form of an integer matrix. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pages 675--687. IEEE Computer Society, 2000.
[13]
P. Elbaz-Vincent. Perfects lattices, homology of modular groups and algebraic K-theory. Oberwolfach Reports (OWR), 2, 2005. based on joint work with H. Gangl and C.Soulé.
[14]
P. Elbaz-Vincent, H. Gangl, and C. Soulé. Perfect forms, cohomology of modular groups and K-theory of the integers. in preparation.
[15]
P. Elbaz-Vincent, H. Gangl,and C. Soulé. Quelques calculs de la cohomologie de GL N (Z etdela K-théorie de Z C. R. Acad. Sci. Paris, Ser.I, 335: 321--324, 2002.
[16]
P. Giorgi, C.-P. Jeannerod, and G. Villard. On the complexity of polynomial matrix computations. In R. Sendra, editor, Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, Philadelphia, Pennsylvania, USA, pages 135--142. ACM Press, New York, Aug. 2003.
[17]
T. Kaczyński, K. Mischaikow,and M. Mrozek. Computational Homology. Springer,2004.
[18]
T.Kaczyński, M. Mrozek, and M. Ślusarek. Homology computation by reduction of chain complexes. Computers and Mathematics, 35(4): 59--70, 1998.
[19]
E. Kaltofen. Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems.Mathematics of Computation, 64(210): 777--806, Apr. 1995.
[20]
E. Kaltofen and A. Lobo. Distributed matrix-free solution of large sparse linear systems over finite fields. In A.Tentner, editor, Proceedings of High Performance Computing 1996, San Diego, California. Society for Computer Simulation, Simulation Councils, Inc., Apr. 1996.
[21]
E. Kaltofen and B.D.Saunders.On Wiedemann's method of solving sparse linear systems. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC '91), volume 539 of Lecture Notes in Computer Science, pages 29--38, Oct. 1991.
[22]
M. Kurihara. Some remarks on conjectures about cyclotomic fields and K-groups of Z Compos. Math., 81(2):223--236, 1992.
[23]
J. Rosenberg. Algebraic K-Theory and its applications. Springer, 1995.
[24]
B. D. Saunders and Z. Wan. Smith normal form of dense integer matrices,fast algorithms into practice. In J. Gutierrez, editor, Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, Santander, Spain, pages 274--281. ACM Press, New York, July 2004.
[25]
C. Soulé. Perfects forms and the Vandiver conjecture. J. reine angew. Math., 517: 209--221, 1999.
[26]
E. H. Spanier. Algebraic Topology. Springer, 1994.
[27]
E. Thomé. Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm. Journal of Symbolic Computations, 33(5): 757--775, July 2002.
[28]
W.J. Turner. A block wiedemann rank algorithm. In Dumas {8}, pages 332--339.
[29]
G. Villard. Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems. In W. W. Kòuchlin, editor, Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, Maui, Hawaii, pages 32--39. ACM Press, New York, July 1997.
[30]
G. Villard. A study of Coppersmith's block Wiedemann algorithm using matrix polynomials. Technical Report 975-IM, LMC/IMAG, Apr. 1997.
[31]
G. Voronoi. Nouvelles applications des paramètres continusàlathéorie des formes quadratiques. J. Crelle, 133: 97--178, 1907.
[32]
D. H. Wiedemann. Solving sparse linear equations over ?nite fields. IEEE Transactions on Information Theory, 32(1): 54--62, Jan. 1986.

Cited By

View all
  • (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
  • (2017)Parallel Sparse PLUQ Factorization modulo pProceedings of the International Workshop on Parallel Symbolic Computation10.1145/3115936.3115944(1-10)Online publication date: 23-Jul-2017
  • (2014)Online order basis algorithm and its impact on the block Wiedemann algorithmProceedings of the 39th International Symposium on Symbolic and Algebraic Computation10.1145/2608628.2608647(202-209)Online publication date: 23-Jul-2014
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PASCO '07: Proceedings of the 2007 international workshop on Parallel symbolic computation
July 2007
116 pages
ISBN:9781595937414
DOI:10.1145/1278177
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 July 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. algebraic K-theory
  2. block Wiedemann
  3. cohomology computation
  4. parallel rank and Smith form
  5. sparse matrix

Qualifiers

  • Article

Conference

ISSAC07
Sponsor:

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (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
  • (2017)Parallel Sparse PLUQ Factorization modulo pProceedings of the International Workshop on Parallel Symbolic Computation10.1145/3115936.3115944(1-10)Online publication date: 23-Jul-2017
  • (2014)Online order basis algorithm and its impact on the block Wiedemann algorithmProceedings of the 39th International Symposium on Symbolic and Algebraic Computation10.1145/2608628.2608647(202-209)Online publication date: 23-Jul-2014
  • (2010)Exact sparse matrix-vector multiplication on GPU's and multicore architecturesProceedings of the 4th International Workshop on Parallel and Symbolic Computation10.1145/1837210.1837224(80-88)Online publication date: 21-Jul-2010
  • (2010)Fifteen years after DSC and WLSS2 what parallel computations I do todayProceedings of the 4th International Workshop on Parallel and Symbolic Computation10.1145/1837210.1837213(10-17)Online publication date: 21-Jul-2010

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media