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.