Show simple item record

dc.contributor.author
Kyng, Rasmus
dc.contributor.author
Zhang, Peng
dc.date.accessioned
2020-09-29T12:25:03Z
dc.date.available
2020-09-26T19:40:12Z
dc.date.available
2020-09-29T12:25:03Z
dc.date.issued
2020
dc.identifier.issn
0097-5397
dc.identifier.issn
1095-7111
dc.identifier.other
10.1137/17M1161774
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/442870
dc.description.abstract
We show that if the nearly linear time solvers for Laplacian matrices and their generalizations can be extended to solve just slightly larger families of linear systems, then they can be used to quickly solve all systems of linear equations over the reals. This result can be viewed either positively or negatively: either nearly linear time algorithms can be developed for solving all systems of linear equations over the reals, or progress on the families that can be solved in nearly linear time will soon halt.
en_US
dc.language.iso
en
en_US
dc.publisher
Society for Industrial and Applied Mathematics
en_US
dc.subject
numerical linear algebra
en_US
dc.subject
linear system solvers
en_US
dc.subject
Laplacian solvers
en_US
dc.subject
multicommodity flow problems
en_US
dc.subject
truss stiffness matrices
en_US
dc.subject
total variation matrices
en_US
dc.subject
complexity theory
en_US
dc.subject
fine-grained complexity
en_US
dc.title
Hardness Results for Structured Linear Systems
en_US
dc.type
Journal Article
dc.date.published
2020-02-18
ethz.journal.title
SIAM Journal on Computing
ethz.journal.volume
49
en_US
ethz.journal.issue
4
en_US
ethz.journal.abbreviated
SIAM j. comput. (Print)
ethz.pages.start
280
en_US
ethz.pages.end
349
en_US
ethz.identifier.wos
ethz.publication.place
Philadelphia, PA
en_US
ethz.publication.status
published
en_US
ethz.date.deposited
2020-09-26T19:40:17Z
ethz.source
WOS
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2020-09-29T12:25:13Z
ethz.rosetta.lastUpdated
2020-09-29T12:25:13Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Hardness%20Results%20for%20Structured%20Linear%20Systems&rft.jtitle=SIAM%20Journal%20on%20Computing&rft.date=2020&rft.volume=49&rft.issue=4&rft.spage=280&rft.epage=349&rft.issn=0097-5397&1095-7111&rft.au=Kyng,%20Rasmus&Zhang,%20Peng&rft.genre=article&
 Search via SFX

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record