Abstrakt. Detta dokument presenterar en effektiv, finkornig parallellalgoritm för att lösa Eikonalekvationen på triangulära maskor. Eikonalekvationen, och den bredare klassen av Hamilton-Jacobi ekvationer som den tillhör, har ett brett spektrum av tillämpningar från geometrisk optik och seismologi till biologisk modellering och analys av geometri och bilder. Förmågan att lösa sådana ekvationer exakt och effektivt ger nya möjligheter för att utforska och visualisera parameterrymder och för att lösa inversa problem som är beroende av sådana ekvationer i framåtmodellen. Effektiva lösare på toppmoderna parallella arkitekturer kräver nya algoritmer som i många fall inte är optimala, men bättre lämpade för synkrona uppdateringar av lösningen. I tidigare arbeten [W. K. Jeong och R. T. Whitaker, SIAM J. Sci. Detta beslut träder i kraft den tjugonde dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. 2512-2534] föreslog författarna den snabba iterativa metoden (FIM) för att effektivt lösa Eikonalekvationen på vanliga rutnät. I detta papper utökar vi den snabba iterativa metoden för att lösa Eikonal ekvationer effektivt på triangulerade domäner på CPU och på parallella arkitekturer, inklusive grafikprocessorer. Vi föreslår ett nytt lokalt uppdateringssystem som tillhandahåller lösningar med första ordningens noggrannhet för båda arkitekturerna. Vi föreslår också ett nytt triangelbaserat uppdateringssystem och dess motsvarande datastruktur för effektiv oegentlig datakartläggning till parallella eninstruktionsprocessorer (SIMD). Vi ger detaljerade beskrivningar av implementationer på en enda CPU, en multicore CPU med delat minne, och SIMD arkitekturer med jämförande resultat mot state-of-the-art Eikonal lösare.
En metod som inte använder en prioriterad kö är snabb iterativ metod REF, som är en algoritmisk ram för att lösa Eikonal ekvation.
A FAST ITERATIVE METHOD FOR SOLVING THE EIKONAL EQUATION ON TRIANGULATED SURFACES ∗
{'venue': 'SIAM journal on scientific computing : a publication of the Society for Industrial and Applied Mathematics', 'journal': 'SIAM journal on scientific computing : a publication of the Society for Industrial and Applied Mathematics', 'mag_field_of_study': ['Computer Science', 'Medicine']}