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
External linksSearch via SFX
Journal / seriesTechnical report / ETH Zurich, Department of Computer Science
PublisherETH, Eidgenössische Technische Hochschule, Department of Computer Science, Institute of Scientific Computing
Organisational unit02150 - Dep. Informatik / Dep. of Computer Science
NotesTechnical Reports D-INFK.
MoreShow all metadata