| Title | Certified dense linear system solving |
| Author(s) | Thom Mulders, Arne Storjohann |
| Type | Article in Journal |
| Abstract | A randomized algorithm is given for solving a system of linear equations over a principal ideal domain. The algorithm returns a solution vector which has minimal denominator. A certificate of minimality is also computed. A given system has a Diophantine solution precisely when the minimal denominator is one. Cost estimates are given for systems over the ring of integers and ring of polynomials with coefficients from a field. |
| Keywords | Linear system solution, Diophantine system solution, Integer matrix, Polynomial matrix, Randomized algorithm, Las Vegas |
| ISSN | 0747-7171 |
| URL |
http://www.sciencedirect.com/science/article/pii/S0747717103001214 |
| Language | English |
| Journal | Journal of Symbolic Computation |
| Volume | 37 |
| Number | 4 |
| Pages | 485 - 510 |
| Year | 2004 |
| Edition | 0 |
| Translation |
No |
| Refereed |
No |
