Mat-1.3656 Numeerisen
analyysin ja laskennallisen tieteen seminaari.
Ma 19.11. 2007
Veikko
Sariola, TKK, Control Engineering Laboratory
O(N) nopea
marssimenetelmä
Nopeat marssimenetelmät ovat vakiintuneet
eikonaaliyhtälön numeeriseksi ratkaisemiseksi. Näiden
menetelmien laskennallinen vaativuus on O(N log N), missä N on
diskretointiverkon solmujen lukumäärä. Hiljattain on
julkaistu nopea marssimenetelmä, jonka vaativuus on vain O(N),
mutta virhe samaa suuruusluokkaa kuin alkuperäisen
menetelmän. Uuden ja vanhan menetelmän tarkkuutta verrataan
yksinkertaisissa tehtävissä, jotka voidaan ratkaista
myös analyyttisesti. Uutta menetelmää sovelletaan
myös laskettaessa pistemäisen valonlähteen varjoja
sekä etsittäessä robotin reittiä. Uusi
menetelmä osoittautuu käytännön
tehtävissä huomattavasti vanhaa menetelmää
nopeammaksi ja virheen muutos on merkityksetön.