Reduction of huge, sparse matrices over finite fields via created catastrophes

Pomerance, Carl; Smith, J. W.

Experiment. Math., Tome 1 (1992) no. 4, p. 89-94 / Harvested from Project Euclid

Résumé

We present a heuristic method for the reduction modulo 2 of a large, sparse bit matrix to a smaller, dense bit matrix that can then be solved by conventional means, such as Gaussian elimination. This method worked effectively for us in reducing matrices as large as 100,000${}\times{}$100,000 to much smaller, but denser square matrices.

Publié le : 1992-05-14
Classification: 65F50

@article{1048709047,
     author = {Pomerance, Carl and Smith, J. W.},
     title = {Reduction of huge, sparse matrices over finite fields via created catastrophes},
     journal = {Experiment. Math.},
     volume = {1},
     number = {4},
     year = {1992},
     pages = { 89-94},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1048709047}
}

Pomerance, Carl; Smith, J. W. Reduction of huge, sparse matrices over finite fields via created catastrophes. Experiment. Math., Tome 1 (1992) no. 4, pp.  89-94. http://gdmltest.u-ga.fr/item/1048709047/