Komputasi Stensil Cepat pada Satu Interval yang Bergerak Secara Arbitrer

Komputasi stensil memperbarui setiap sel grid dari nilai tetangganya pada langkah waktu sebelumnya. Menyimulasikan T langkah pada N sel secara langsung membutuhkan $\Theta (NT)$. Serangkaian penelitian yang dimulai oleh Ahmad et al. menurunkan biaya ini dengan menyusun banyak langkah waktu menjadi satu operator linear dan menerapkannya melalui Fast Fourier Transform (FFT). Namun, teknik ini memerlukan pengetahuan tentang sel mana yang masih mematuhi operator yang sama saat langkah tersusun berakhir. Pada masalah batas bebas, region ini ditentukan oleh solusi dan bergerak seiring evolusinya, sehingga penyusunan menjadi sulit.

Makalah ini mempelajari satu dimensi spasial, stensil tiga titik dengan koefisien yang berubah terhadap waktu, dan region terhitung yang merupakan satu interval yang kedua titik ujungnya bergerak dengan besaran arbitrer pada setiap langkah, yang diungkapkan secara online. Parameter kuncinya adalah $B$, yaitu horizon ditambah variasi total lintasan batas. Hasil utamanya adalah jadwal dengan kerja $O((B+N)\log T\log (N+B))$ dan span $O(T\log T\log (N+B))$, dengan nilai terhitung yang eksak. Ini memperbaiki batas terbaik yang ada, yang mensyaratkan batas bergera

Hasil utamanya adalah jadwal dengan kerja $O((B+N)\log T\log (N+B))$ dan span $O(T\log T\log (N+B))$, dengan $B$ adalah horizon ditambah variasi total lintasan batas. Nilai terhitungnya eksak. Ini memperbaiki batas terbaik sebelumnya, yang mensyaratkan batas bergerak paling banyak satu sel per langkah waktu. Untuk batas yang mematuhi pembatasan tersebut, $B\le 3T$, sehingga batas baru ini nyaris linear pada semua lintasan yang dicakup hasil sebelumnya. Secara umum, $B$ hanya bertambah sebesar jarak yang benar-benar ditempuh batas; misalnya, satu lompatan dengan lebar $N$ berbiaya $T+2N$.

Batas tersebut ketat dalam arti bahwa dengan $p$ region, kerja memburuk sebesar faktor $p$. Pada $p=\sqrt{T}$, terdapat instans dengan kerja $\Theta (T^{3/2})$ sementara $B+N=\Theta (T)$. Ini menunjukkan bahwa pendekatan variasi total tidak dapat dilonggarkan ke banyak region tanpa kehilangan.

Semua hasil diperiksa mesin di Lean 4, kecuali batas konvolusi klasik, yang diimpor sebagai antarmuka. Ini memberikan keyakinan tinggi terhadap kebenaran pembuktian.