Carnegie-Mellon-Universität stellt superschnellen Algorithmus für lineare Gleichungssysteme vor (Software)

Martin Vogel ⌂ @, Dortmund / Bochum, Freitag, 22.10.2010, 16:51 (vor 3222 Tagen)

Eine Geschwindigkeitssteigerung um mehrere Zehnerpotenzen verspricht ein neuer Algorithmus zur Lösung linearer Gleichungssysteme, der von Ioannis Koutis, Gary L. Miller und Richard Peng an der Carnegie-Mellon-Universität in Pennsylvania entwickelt wurde. Während beispielsweise beim Gauß’schen Eliminationsverfahren die Zeit zur Lösung mit der dritten Potenz der Gleichungsanzahl wächst (t ∼ s³), steigt sie beim neuen Verfahren lediglich proportional zum Quadrat des Logarithmus der Gleichungsanzahl an (t ∼ log²(s)). Ein Gleichungssystem mit einer Million Unbekannten sei so in einem Milliardstel der Rechenzeit lösbar, schreiben die Autoren. Sie weisen aber ehrlicherweise darauf hin, dass es bessere Algorithmen als das olle Gauß-Verfahren gibt und dass ihre Schätzung nicht den maximalen, sondern den vermuteten typischen Zeitaufwand wiedergibt.

http://www.cmu.edu/news/archive/2010/October/oct21_speedyalgorithm.shtml

--
Dipl.-Ing. Martin Vogel
Leiter des Bauforums

Heute schon programmiert? Einführung in Python 3 (PDF)



gesamter Thread:

 RSS-Feed dieser Diskussion

powered by my little forum