Rights / licenseIn Copyright - Non-Commercial Use Permitted
The following problems related to linear systems are studied: finding a diophantine solution; finding a rational solution; proving no diophantine solution exists; proving no rational solution exists. These problems are reduced, via randomization, to that of computing an expected constant number of rational solutions of square nonsingular systems using adic lifting. The bit complexity of the latter problem is improved by incorporating fast arithmetic and fast matrix multiplication. The resulting randomized algorithm for certified dense linear system solving has substantially better asymptotic complexity than previous algorithms for either rational or diophantine linear system solving Show more
Journal / seriesTechnical report / Department of Computer Science, ETH Zurich
PublisherETH, Eidgenössische Technische Hochschule, Department of Computer Science, Institute of Scientific Computing
Organisational unit02150 - Departement Informatik / Department of Computer Science
NotesTechnical Reports D-INFK.
MoreShow all metadata