Abstract | ||
---|---|---|
We propose a new algorithm to solve sparse linear systems of equa- tions over the integers. This algorithm is based on a p-adic lifting tech- nique combined with the use of block matrices with structured blocks. It achieves a sub-cubic complexity in terms of machine operations subject to a conjecture on the effectiveness of certain sparse projections. A LinBox- based implementation of this algorithm is demonstrated, and emphasizes the practical benefits of this new method over the previous state of the art. |
Year | Venue | Keywords |
---|---|---|
2006 | Clinical Orthopaedics and Related Research | symbolic computation,linear system |
Field | DocType | Volume |
Integer,Combinatorics,Sparse language,System of linear equations,Linear system,Matrix (mathematics),Sparse approximation,Theoretical computer science,Quantum algorithm for linear systems of equations,Mathematics,Matrix-free methods | Journal | abs/cs/060 |
Citations | PageRank | References |
2 | 0.38 | 17 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Wayne Eberly | 1 | 131 | 14.86 |
Mark Giesbrecht | 2 | 214 | 23.54 |
Pascal Giorgi | 3 | 234 | 18.02 |
Arne Storjohann | 4 | 2 | 0.38 |
Gilles Villard | 5 | 565 | 48.04 |