Show simple item record

dc.contributor.author
Mulders, Thom
dc.contributor.author
Storjohann, Arne
dc.date.accessioned
2017-11-03T17:11:10Z
dc.date.available
2017-06-10T18:34:50Z
dc.date.available
2017-11-03T17:11:10Z
dc.date.issued
2000
dc.identifier.uri
http://hdl.handle.net/20.500.11850/68735
dc.identifier.doi
10.3929/ethz-a-006654225
dc.description.abstract
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.
en_US
dc.language.iso
en
en_US
dc.publisher
ETH, Eidgenössische Technische Hochschule, Department of Computer Science, Institute of Scientific Computing
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.title
Certified dense linear system solving
en_US
dc.type
Report
dc.rights.license
In Copyright - Non-Commercial Use Permitted
ethz.journal.title
Technical Report / ETH Zurich, Department of Computer Science
ethz.journal.volume
355
en_US
ethz.size
36 p.
en_US
ethz.code.ddc
0 - Computer science, information & general works::004 - Data processing, computer science
en_US
ethz.notes
Technical Reports D-INFK.
en_US
ethz.identifier.nebis
006654225
ethz.publication.place
Zürich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science
en_US
ethz.date.deposited
2017-06-10T18:36:44Z
ethz.source
ECOL
ethz.source
ECIT
ethz.identifier.importid
imp593650bdf12ec34612
ethz.identifier.importid
imp59366b0cae55882069
ethz.ecolpid
eth:4394
ethz.ecitpid
pub:109082
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-08-01T12:23:26Z
ethz.rosetta.lastUpdated
2017-11-03T17:11:14Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Certified%20dense%20linear%20system%20solving&rft.jtitle=Technical%20Report%20/%20ETH%20Zurich,%20Department%20of%20Computer%20Science&rft.date=2000&rft.volume=355&rft.au=Mulders,%20Thom&Storjohann,%20Arne&rft.genre=report&
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record