Loading...
Please wait, while we are loading the content...
Similar Documents
computational complexity FAST COMPUTATION OF THE SMITH FORM OF A SPARSE INTEGER MATRIX
| Content Provider | CiteSeerX |
|---|---|
| Author | Giesbrecht, Mark |
| Abstract | Abstract. We present a new probabilistic algorithm to compute the Smith normal form of a sparse integer matrix A ∈ Z m×n. The algorithm treats A as a “black box”—A is only used to compute matrix-vector products and we do not access individual entries in A directly. The algorithm requires about O(m2 log �A�) black box eval-, plus uations w ↦ → Aw mod p for word-sized primes p and w ∈ Zn×1 p O(m2n log �A � + m3 log 2 �A�) additional bit operations. For sparse matrices this represents a substantial improvement over previously known algorithms. The new algorithm suffers from no “fill-in ” or intermediate value explosion, and uses very little additional space. We also present an asymptotically fast algorithm for dense matrices which requires about O(n · MM(m) log �A � + m3 log2 �A�) bit operations, where O(MM(m)) operations are sufficient to multiply two m × m matrices over a field. Both algorithms are probabilistic of the Monte Carlo type—on any input they return the correct answer with a controllable, exponentially small probability of error. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Computational Complexity Fast Computation Sparse Integer Matrix Smith Form Bit Operation Intermediate Value Explosion Monte Carlo Type Substantial Improvement Little Additional Space Additional Bit Operation Word-sized Prime Small Probability Access Individual Entry Smith Normal Form New Algorithm Suffers Correct Answer New Probabilistic Algorithm Sparse Integer Black Box Eval Black Box Dense Matrix M3 Log Sparse Matrix Matrix-vector Product |
| Content Type | Text |
| Resource Type | Article |
