$\displaystyle=\begin{pmatrix}r_{1}\cos\big{(}0.5\pi(\eta+1)\big{)}\\\
r_{1}\sin\big{(}0.5\pi(\eta+1)\big{)}\end{pmatrix}$ (A.1b)
$\displaystyle\boldsymbol{e}_{3}(\xi,\eta)$
$\displaystyle=\begin{pmatrix}-r_{0}-0.5(r_{1}-r_{0})(\xi+1)\\\
0\end{pmatrix}$ (A.1c) $\displaystyle\boldsymbol{e}_{4}(\xi,\eta)$
$\displaystyle=\begin{pmatrix}r_{0}\cos\big{(}0.5\pi(\eta+1)\big{)}\\\
r_{0}\sin\big{(}0.5\pi(\eta+1)\big{)}\end{pmatrix}$ (A.1d)

where the edges $\boldsymbol{e}_{i}$ of the $[-1,1]^{2}$ cube are labeled
counter-clockwise starting from the bottom $(\xi,\eta=0)$ edge. This mapping
corresponds to a half-circle with radius $r_{1}$ from which a half-circle with
radius $r_{0}$ is subtracted. The mesh is discretized using $N_{\xi}=192\times
N_{\eta}=128$ cells and is displayed in Fig. 13.

Figure 13: High-resolution, structured mesh for demonstration of working PERK
schemes on smooth meshes.

For this testcase we simulate the inviscid Euler equations of gas dynamics
with $\gamma=1.4$ with initial condition

$\boldsymbol{u}_{\text{prim}}(t_{0}=0,x,y)=\begin{pmatrix}\rho\\\ v_{x}\\\
v_{y}\\\ p\end{pmatrix}=\begin{pmatrix}1.0\\\ 0.0\\\ 0.0\\\
1.0+2^{-\frac{(x-0.6r_{1})^{2}+y^{2}}{0.45^{2}}}\end{pmatrix}$ (A.2)

which corresponds to a pressure perturbation with magnitude $p_{\text{max}}=2$
located at the right-bottom of the half-circle, cf. Fig. 14a.

In terms of spatial discretization we employ the dgsem with $k=2$ local
polynomials, hll surface-flux and an entropy-conservative volume flux [70, 66]
with reflective boundaires. In particular, no techniques like shock capturing
or positivity-preserving limiters are employed to suppress spurious
oscillations.

For time-integration, second-order accurate stability polynomials with degrees
$S=\allowbreak\\{4,\allowbreak 6,\allowbreak 8,\allowbreak\dots,\allowbreak
16\\}$ are optimized, based on which we construct a range of PERK schemes. The
gridcells are sorted into $R$ (number of PERK family members) bins based on
their minimum edge length which govern the associated Runge-Kutta method. We
test all combinations of PERK schemes with $E^{(1)}=4$ minimum stage
evaluations, i.e., from the standalone $S=4$ scheme up to the
$S=16,E=\\{4,6,8,\dots,16\\}$ family. For all combinations, the maximum
admissible timestep is increased according to highest number of stage
evaluations $E^{(R)}$. For this setup, across different PERK schemes, the
stage-evaluation normalized CFL-number for stable simulation is essentially
constant across PERK families, as shown in Table 13. For the sake of
completeness we also provide the speedup compared to the Shu-Osher $p=3,S=3$
scheme, the reference method from [1, 2] in Table 13.

$E^{(R)}$ | 4 | 6 | 8 | 10 | 12 | 14 | 16
---|---|---|---|---|---|---|---
$\text{CFL}\cdot\frac{E^{(1)}}{E^{(R)}}$ | $0.95$ | $0.97$ | $0.97$ | $0.94$ | $0.94$ | $0.94$ | $0.93$
$\frac{\tau_{\text{SSP}_{3;3}}}{\tau_{\text{P-ERK}_{2;4,\dots,E^{(R)}}}}$ | $1.26$ | $1.64$ | $1.90$ | $2.06$ | $2.22$ | $2.37$ | $2.45$
Table 13: Normalized CFL numbers and speedup across different PERK schemes for
the structured mesh testcase. Here, $E^{(1)}=4$ is the base scheme utilized in
all cases.

For illustration, the final pressure distribution $p$ at $t_{f}=5.0$ is
displayed in Fig. 14 alongside the initial perturbation according to (A.2).

(a) Initial pressure perturbation according to A.2.

(b) Pressure $p$ at final time $t_{f}=5.0$.

Figure 14: Initial pressure perturbation according to A.2 (Fig. 14a) and
pressure $p$ at final time $t_{f}=5.0$ (Fig. 14b).

We repeated this testcase for a significantly coarser mesh with
$N_{\xi}=48\times N_{\eta}=32$ cells and obtained qualitatively similar
results. In particular, the normalized CFL number is again of similar value,
with the largest value $\text{CFL}=1.04$ for the PERK scheme with $E^{(R)}=10$
and smallest value for $E^{(R)}=16$ with $\text{CFL}=0.95$.

This example demonstrates that the PERK schemes are a suitable multirate
scheme, even for inviscid problems without stabilization. In particular, due
to the smooth meshes, the discontinuity in the mesh is effectively eliminated
and does not coincide with the discontinuity in the time integration method.
This is the main difference to quad/octree-basedAMR meshes where the
discontinuity in the mesh coincides with the discontinuity in the time
integration method. In this case, the mesh refinement factor is always
$\alpha=2$ and the difference in stage evaluations scales quadratically with
the number of levels, leading to a discontinuity in methods for the finest
levels.

##  Appendix B Ideal MHD Rotor: Initial Condition

For the simulation of the ideal MHD rotor we employ the initial condition from
[95]. The radius $r_{0}$ of the spinning cylinder is set to $r_{0}=0.1$ while
the medium is initially at rest for $r\geq r_{1}=0.115$ with radius
$r(x,y)=\sqrt{(x-0.5)^{2}+(y-0.5)^{2}}$. The magnetic field is set uniformly
to
$\boldsymbol{B}(t_{0}=0,x,y)=\begin{pmatrix}\frac{5}{2\sqrt{\pi}}&0&0\end{pmatrix}$
as well as pressure $p(0,x,y)=1$ and $v_{z}(0,x,y)=0$. Inside the spinning
cylinder, i.e., $r\leq r_{0}$ we set the density to $\rho(0,x,y)=10$ and the
velocities to $v_{x}(0,x,y)=-20(y-0.5)$, $v_{y}(0,x,y)=20(x-0.5)$. In the
transition from $r_{0}$ to $r_{1}$ we set the density to
$\rho(0,x,y)=1+9f\big{(}r(x,y)\big{)}$ and the velocities to
$v_{x}(0,x,y)=-20(y-0.5)f\big{(}r(x,y)\big{)}$,
$v_{y}(0,x,y)=20(x-0.5)f\big{(}r(x,y)\big{)}$ with
$f\big{(}r(x,y)\big{)}\coloneqq\frac{r_{1}-r(x,y)}{r_{1}}$. Outside of
$r_{1}$, i.e., $r>r_{1}$ the medium is at rest $v_{x}(t_{0},x,y)=0$,
$v_{y}(t_{0},x,y)=0$ and density is set to $\rho(0,x,y)=1$.

## References

  * Vermeire [2019] B. C. Vermeire,  Paired explicit Runge-Kutta schemes for stiff systems of equations,  Journal of Computational Physics 393 (2019) 465–483. doi:10.1016/j.jcp.2019.05.014.
  * Nasab and Vermeire [2022] S. H. Nasab, B. C. Vermeire,  Third-order paired explicit Runge-Kutta schemes for stiff systems of equations,  Journal of Computational Physics 468 (2022) 111470. doi:10.1016/j.jcp.2022.111470.
  * Godlewski and Raviart [2013] E. Godlewski, P.-A. Raviart, Numerical approximation of hyperbolic systems of conservation laws, volume 118 of Applied Mathematical Sciences, 2 ed., Springer Science & Business Media, 2013. doi:10.1007/978-1-0716-1344-3.
  * Berger and Oliger [1984] M. J. Berger, J. Oliger,  Adaptive mesh refinement for hyperbolic partial differential equations,  Journal of Computational Physics 53 (1984) 484–512. doi:10.1016/0021-9991(84)90073-1.
  * Cockburn and Shu [2001] B. Cockburn, C.-W. Shu,  Runge–Kutta discontinuous Galerkin methods for convection-dominated problems,  Journal of Scientific Computing 16 (2001) 173–261. doi:10.1023/A:1012873910884.
  * Courant et al. [1967] R. Courant, K. Friedrichs, H. Lewy,  On the partial difference equations of mathematical physics,  IBM Journal of Research and Development 11 (1967) 215–234. doi:10.1147/rd.112.0215.
  * Rentrop [1985] P. Rentrop,  Partitioned Runge-Kutta methods with stiffness detection and stepsize control,  Numerische Mathematik 47 (1985) 545–564. doi:10.1007/BF01389456.
  * Bruder et al. [1988] J. Bruder, K. Strehmel, R. Weiner,  Partitioned adaptive Runge-Kutta methods for the solution of nonstiff and stiff systems,  Numerische Mathematik 52 (1988) 621–638. doi:10.1007/BF01395815.
  * Günther et al. [2001] M. Günther, A. Kvaernø, P. Rentrop,  Multirate partitioned Runge-Kutta methods,  BIT Numerical Mathematics 41 (2001) 504–514. doi:10.1023/A:1021967112503.
  * Constantinescu and Sandu [2007] E. M. Constantinescu, A. Sandu,  Multirate timestepping methods for hyperbolic conservation laws,  Journal of Scientific Computing 33 (2007) 239–278. doi:10.1007/s10915-007-9151-y.
  * Grote et al. [2015] M. J. Grote, M. Mehlin, T. Mitkova,  Runge–Kutta-based explicit local time-stepping methods for wave propagation,  SIAM Journal on Scientific Computing 37 (2015) A747–A775. doi:10.1137/140958293.
  * Krivodonova [2010] L. Krivodonova,  An efficient local time-stepping scheme for solution of nonlinear conservation laws,  Journal of Computational Physics 229 (2010) 8537–8551. doi:10.1016/j.jcp.2010.07.037.
  * Schlegel et al. [2009] M. Schlegel, O. Knoth, M. Arnold, R. Wolke,  Multirate Runge–Kutta schemes for advection equations,  Journal of Computational and Applied Mathematics 226 (2009) 345–357. doi:10.1016/j.cam.2008.08.009.
  * Günther and Sandu [2016] M. Günther, A. Sandu,  Multirate generalized additive Runge-Kutta methods,  Numerische Mathematik 133 (2016) 497–524. doi:10.1007/s00211-015-0756-z.
  * Cooper and Sayfy [1983] G. J. Cooper, A. Sayfy,  Additive Runge-Kutta methods for stiff ordinary differential equations,  Mathematics of Computation 40 (1983) 207–218. doi:10.1090/S0025-5718-1983-0679441-1.
  * Jenny [2020] P. Jenny,  Time adaptive conservative finite volume method,  Journal of Computational Physics 403 (2020) 109067. doi:10.1016/j.jcp.2019.109067.
  * Ascher et al. [1995] U. M. Ascher, S. J. Ruuth, B. T. Wetton,  Implicit-explicit methods for time-dependent partial differential equations,  SIAM Journal on Numerical Analysis 32 (1995) 797–823. doi:10.1137/0732037.
  * Hairer [1981] E. Hairer,  Order conditions for numerical methods for partitioned ordinary differential equations,  Numerische Mathematik 36 (1981) 431–445. doi:10.1007/BF01395956.
  * Hundsdorfer et al. [2015] W. Hundsdorfer, D. I. Ketcheson, I. Savostianov,  Error analysis of explicit partitioned Runge-Kutta schemes for conservation laws,  Journal of Scientific Computing 63 (2015) 633–653. doi:10.1007/s10915-014-9906-1.
  * Higueras [2006] I. Higueras,  Strong stability for additive Runge–Kutta methods,  SIAM Journal on Numerical Analysis 44 (2006) 1735–1758. doi:10.1137/040612968.
  * Higueras [2009] I. Higueras,  Characterizing strong stability preserving additive Runge-Kutta methods,  Journal of Scientific Computing 39 (2009) 115–128. doi:10.1007/s10915-008-9252-2.
  * Hundsdorfer et al. [2007] W. Hundsdorfer, A. Mozartova, V. Savcenco, Analysis of explicit multirate and partitioned Runge-Kutta schemes for conservation laws, Technical Report, Centrum voor Wiskunde en Informatica, 2007. URL: https://research.tue.nl/en/publications/analysis-of-explicit-multirate-and-partitioned-{R}unge-{K}utta-scheme, cWI report. MAS-E; Vol. 0715.
  * Ketcheson et al. [2013] D. I. Ketcheson, C. B. MacDonald, S. J. Ruuth,  Spatially partitioned embedded Runge–Kutta methods,  SIAM Journal on Numerical Analysis 51 (2013) 2887–2910. doi:10.1137/130906258.
  * Doehring et al. [2024] D. Doehring, M. Schlottke-Lakemper, G. J. Gassner, M. Torrilhon, Reproducibility repository for ”Multirate time-integration based on dynamic ode partitioning through adaptively refined meshes for compressible fluid dynamics”, https://github.com/trixi-framework/paper-2024-amr-paired-rk, 2024. doi:https://doi.org/10.5281/zenodo.10792779.
  * Hairer et al. [1993] E. Hairer, G. Wanner, S. P. Nørsett, Solving Ordinary Differential Equations I: Nonstiff Problems, Springer Series in Computational Mathematics, 2 ed., Springer Berlin, Heidelberg, 1993. doi:10.1007/978-3-540-78862-1.
  * Hofer [1976] E. Hofer,  A partially implicit method for large stiff systems of odes with only few equations introducing small time-constants,  SIAM Journal on Numerical Analysis 13 (1976) 645–663. URL: 10.1137/0713054. doi:10.1137/0713054. arXiv:10.1137/0713054.
  * Griepentrog [1978] E. Griepentrog,  Gemischte Runge-Kutta-verfahren für steife systeme,  Seminarbereicht Sekt. Math (1978) 19–29.
  * Jay [1996] L. Jay,  Symplectic partitioned Runge-Kutta methods for constrained Hamiltonian systems,  SIAM Journal on Numerical Analysis 33 (1996) 368–387. URL: 10.1137/0733019. doi:10.1137/0733019. arXiv:10.1137/0733019.
  * Abia and Sanz-Serna [1993] L. Abia, J. Sanz-Serna,  Partitioned Runge-Kutta methods for separable Hamiltonian problems,  mathematics of Computation 60 (1993) 617–634. doi:10.1090/S0025-5718-1993-1181328-1.
  * Kennedy and Carpenter [2003] C. A. Kennedy, M. H. Carpenter,  Additive Runge–Kutta schemes for convection–diffusion–reaction equations,  Applied Numerical Mathematics 44 (2003) 139–181. URL: https://www.sciencedirect.com/science/article/pii/S0168927402001381. doi:10.1016/S0168-9274(02)00138-1.
  * Sandu and Günther [2015] A. Sandu, M. Günther,  A generalized-structure approach to additive Runge–Kutta methods,  SIAM Journal on Numerical Analysis 53 (2015) 17–42. doi:10.1137/130943224.
  * Albrecht [1987] P. Albrecht,  A new theoretical approach to Runge–Kutta methods,  SIAM Journal on Numerical Analysis 24 (1987) 391–406. doi:10.1137/0724030.
  * Jackiewicz and Vermiglio [2000] Z. Jackiewicz, R. Vermiglio,  Order conditions for partitioned Runge-Kutta methods,  Applications of Mathematics 45 (2000) 301–316. URL: http://dml.cz/dmlcz/134441.
  * Wanner and Hairer [1996] G. Wanner, E. Hairer, Solving ordinary differential equations II: Stiff and Differential-Algebraic Problems, volume 375 of Springer Series in Computational Mathematics, 2 ed., Springer Berlin, Heidelberg, 1996. doi:10.1007/978-3-642-05221-7.
  * McLachlan et al. [2011] R. I. McLachlan, Y. Sun, P. Tse,  Linear stability of partitioned Runge–Kutta methods,  SIAM Journal on Numerical Analysis 49 (2011) 232–263. doi:10.1137/100787234.
  * Hespanha [2018] J. P. Hespanha, Linear systems theory, 2 ed., Princeton University press, 2018. URL: https://press.princeton.edu/books/hardcover/9780691179575/linear-systems-theory.
  * Shu and Osher [1988] C.-W. Shu, S. Osher,  Efficient implementation of essentially non-oscillatory shock-capturing schemes,  Journal of Computational Physics 77 (1988) 439–471. doi:10.1016/0021-9991(88)90177-5.
  * Gottlieb et al. [2011] S. Gottlieb, D. Ketcheson, C.-W. Shu, Strong stability preserving Runge-Kutta and multistep time discretizations, World Scientific, 2011. doi:10.1142/9789814289276_0001.
  * Kraaijevanger [1991] J. F. B. M. Kraaijevanger,  Contractivity of Runge-Kutta methods,  BIT Numerical Mathematics 31 (1991) 482–528. doi:10.1007/BF01933264.
  * Kubatko et al. [2014] E. J. Kubatko, B. A. Yeager, D. I. Ketcheson,  Optimal strong-stability-preserving Runge–Kutta time discretizations for discontinuous Galerkin methods,  Journal of Scientific Computing 60 (2014) 313–344. doi:10.1007/s10915-013-9796-7.
  * Ralston [1962] A. Ralston,  Runge-Kutta methods with minimum error bounds,  Mathematics of Computation 16 (1962) 431–437. doi:10.1090/S0025-5718-1962-0150954-0.
  * Ketcheson and Ahmadia [2013] D. Ketcheson, A. Ahmadia,  Optimal stability polynomials for numerical integration of initial value problems,  Communications in Applied Mathematics and Computational Science 7 (2013) 247–271. doi:10.2140/camcos.2012.7.247.
  * Jeltsch and Nevanlinna [1978] R. Jeltsch, O. Nevanlinna,  Largest disk of stability of explicit Runge-Kutta methods,  BIT Numerical Mathematics 18 (1978) 500–502. doi:10.1007/BF01932030.
  * Owren and Seip [1990] B. Owren, K. Seip,  Some stability results for explicit Runge-Kutta methods,  BIT Numerical Mathematics 30 (1990) 700–706. doi:10.1007/BF01933217.
  * Abdulle [2011] A. Abdulle, Explicit stabilized Runge-Kutta methods, Technical Report, Mathematics Institute of Computational Science and Engineering, School of Basic Sciences - Section of Mathematics EPFL Lausanne, 2011. URL: https://www.epfl.ch/labs/mathicse/wp-content/uploads/2018/10/27.2011_AA.pdf.
  * Van der Houwen [1996] P. Van der Houwen,  The development of Runge-Kutta methods for partial differential equations,  Applied Numerical Mathematics 20 (1996) 261–272. doi:10.1016/0168-9274(95)00109-3.
  * Verwer et al. [2004] J. G. Verwer, B. P. Sommeijer, W. Hundsdorfer,  RKC time-stepping for advection–diffusion–reaction problems,  Journal of Computational Physics 201 (2004) 61–79. doi:10.1016/j.jcp.2004.05.002.
  * Torrilhon and Jeltsch [2007] M. Torrilhon, R. Jeltsch,  Essentially optimal explicit Runge-Kutta methods with application to hyperbolic–parabolic equations,  Numerische Mathematik 106 (2007) 303–334. doi:10.1007/s00211-006-0059-5.
  * Ferracina and Spijker [2005] L. Ferracina, M. Spijker,  An extension and analysis of the Shu-Osher representation of Runge-Kutta methods,  Mathematics of Computation 74 (2005) 201–219. doi:10.1090/S0025-5718-04-01664-3.
  * Harten [1997] A. Harten,  High resolution schemes for hyperbolic conservation laws,  Journal of Computational Physics 135 (1997) 260–278. URL: https://www.sciencedirect.com/science/article/pii/S0021999197957132. doi:10.1006/jcph.1997.5713.
  * Gottlieb and Shu [1998] S. Gottlieb, C.-W. Shu,  Total variation diminishing Runge-Kutta schemes,  Mathematics of Computation 67 (1998) 73–85. doi:ttps://doi.org/10.1090/S0025-5718-98-00913-2.
  * LeVeque [2002] R. J. LeVeque, Finite volume methods for hyperbolic problems, volume 31 of Cambridge Texts in Applied Mathematics, Cambridge university press, 2002. doi:10.1017/CBO9780511791253.
  * Zhang and Shu [2011] X. Zhang, C.-W. Shu,  Maximum-principle-satisfying and positivity-preserving high-order schemes for conservation laws: Survey and new developments,  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467 (2011) 2752–2776. URL: https://royalsocietypublishing.org/doi/abs/10.1098/rspa.2011.0153. doi:10.1098/rspa.2011.0153. arXiv:https://royalsocietypublishing.org/doi/pdf/10.1098/rspa.2011.0153.
  * Wang et al. [2013] Z. J. Wang, K. Fidkowski, R. Abgrall, F. Bassi, D. Caraeni, A. Cary, H. Deconinck, R. Hartmann, K. Hillewaert, H. T. Huynh, et al.,  High-order CFD methods: Current status and perspective,  International Journal for Numerical Methods in Fluids 72 (2013) 811–845. doi:10.1002/fld.3767.
  * Sanderse and Veldman [2019] B. Sanderse, A. E. Veldman,  Constraint-consistent Runge–Kutta methods for one-dimensional incompressible multiphase flow,  Journal of Computational Physics 384 (2019) 170–199. doi:10.1016/j.jcp.2019.02.001.
  * Ketcheson et al. [2014] D. I. Ketcheson, L. Lóczi, M. Parsani,  Internal error propagation in explicit Runge-Kutta methods,  SIAM Journal on Numerical Analysis 52 (2014) 2227–2249. doi:10.1137/130936245.
  * Ranocha et al. [2022] H. Ranocha, M. Schlottke-Lakemper, A. R. Winters, E. Faulhaber, J. Chan, G. Gassner,  Adaptive numerical simulations with Trixi.jl: A case study of Julia for scientific computing,  Proceedings of the JuliaCon Conferences 1 (2022) 77. doi:10.21105/jcon.00077. arXiv:2108.06476.
  * Schlottke-Lakemper et al. [2021a] M. Schlottke-Lakemper, A. R. Winters, H. Ranocha, G. Gassner,  A purely hyperbolic discontinuous Galerkin approach for self-gravitating gas dynamics,  Journal of Computational Physics 442 (2021a) 110467. doi:10.1016/j.jcp.2021.110467. arXiv:2008.10593.
  * Schlottke-Lakemper et al. [2021b] M. Schlottke-Lakemper, G. Gassner, H. Ranocha, A. R. Winters, J. Chan, Trixi.jl: Adaptive high-order numerical simulations of hyperbolic PDEs in Julia, https://github.com/trixi-framework/Trixi.jl, 2021b. doi:10.5281/zenodo.3996439.
  * Doehring et al. [2024] D. Doehring, G. J. Gassner, M. Torrilhon, Many-stage optimal stabilized Runge-Kutta methods for hyperbolic partial differential equations, 2024. arXiv:2402.12140, preprint; accepted in revised form for publication in Journal of Scientific Computing.
  * Lehoucq et al. [1998] R. B. Lehoucq, D. C. Sorensen, C. Yang, ARPACK users’ guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods, SIAM, 1998. doi:10.1137/1.9780898719628.
  * Rueda-Ramírez and Gassner [2021] A. M. Rueda-Ramírez, G. J. Gassner,  A subcell finite volume positivity-preserving limiter for DGSEM discretizations of the Euler equations,  arXiv preprint arXiv:2102.06017 (2021). doi:10.48550/arXiv.2102.06017.
  * Black [1999] K. Black,  A conservative spectral element method for the approximation of compressible fluid flow,  Kybernetika 35 (1999) 133–146. URL: https://www.kybernetika.cz/content/1999/1/133/paper.pdf.
  * Kopriva [2009] D. A. Kopriva, Implementing spectral methods for partial differential equations: Algorithms for scientists and engineers, Scientific Computation (SCIENTCOMP), 1 ed., Springer Science & Business Media, 2009. doi:10.1007/978-90-481-2261-5.
  * Gassner [2013] G. J. Gassner,  A skew-symmetric discontinuous Galerkin spectral element discretization and its relation to SBP-SAT finite difference methods,  SIAM Journal on Scientific Computing 35 (2013) A1233–A1253. doi:10.1137/120890144.
  * Gassner et al. [2016] G. J. Gassner, A. R. Winters, D. A. Kopriva,  Split form nodal discontinuous Galerkin schemes with summation-by-parts property for the compressible Euler equations,  Journal of Computational Physics 327 (2016) 39–66. doi:10.1016/j.jcp.2016.09.013.
  * Einfeldt [1988] B. Einfeldt,  On Godunov-type methods for gas dynamics,  SIAM Journal on Numerical Analysis 25 (1988) 294–318. doi:10.1137/0725021.
  * Hennemann et al. [2021] S. Hennemann, A. M. Rueda-Ramírez, F. J. Hindenlang, G. J. Gassner,  A provably entropy stable subcell shock capturing approach for high order split form DG for the compressible Euler equations,  Journal of Computational Physics 426 (2021) 109935. doi:10.1016/j.jcp.2020.109935.
  * Fisher and Carpenter [2013] T. C. Fisher, M. H. Carpenter,  High-order entropy stable finite difference schemes for nonlinear conservation laws: Finite domains,  Journal of Computational Physics 252 (2013) 518–557. doi:10.1016/j.jcp.2013.06.014.
  * Ranocha [2020] H. Ranocha,  Entropy conserving and kinetic energy preserving numerical methods for the Euler equations using summation-by-parts operators,  Spectral and high order methods for partial differential equations ICOSAHOM 2018 134 (2020) 525–535. URL: https://library.oapen.org/handle/20.500.12657/41274. doi:10.1007/978-3-030-39647-3.
  * Toro et al. [1994] E. F. Toro, M. Spruce, W. Speares,  Restoration of the contact surface in the HLL-Riemann solver,  Shock Waves 4 (1994) 25–34. doi:10.1007/BF01414629.
  * Hundsdorfer and Verwer [2010] W. H. Hundsdorfer, J. G. Verwer, Numerical solution of time-dependent advection-diffusion-reaction equations, volume 33 of Springer Series in Computational Mathematics, 1 ed., Springer, 2010. doi:10.1007/978-3-662-09017-6.
  * Burstedde et al. [2011] C. Burstedde, L. C. Wilcox, O. Ghattas,  p4est: Scalable algorithms for parallel adaptive mesh refinement on forests of octrees,  SIAM Journal on Scientific Computing 33 (2011) 1103–1133. doi:10.1137/100791634.
  * Kopriva [1996] D. A. Kopriva,  A conservative staggered-grid Chebyshev multidomain method for compressible flows. II. A semi-structured method,  Journal of Computational Physics 128 (1996) 475–488. doi:10.1006/jcph.1996.0225.
  * Rackauckas and Nie [2017] C. Rackauckas, Q. Nie,  DifferentialEquations.jl – a performant and feature-rich ecosystem for solving differential equations in julia,  The Journal of Open Research Software 5 (2017). URL: https://app.dimensions.ai/details/publication/pub.1085583166andhttp://openresearchsoftware.metajnl.com/articles/10.5334/jors.151/galley/245/download/. doi:10.5334/jors.151, exported from https://app.dimensions.ai on 2019/05/05.
  * Toulorge and Desmet [2012] T. Toulorge, W. Desmet,  Optimal Runge–Kutta schemes for discontinuous Galerkin space discretizations applied to wave propagation problems,  Journal of Computational Physics 231 (2012) 2067–2091. doi:10.1016/j.jcp.2011.11.024.
  * Parsani et al. [2013] M. Parsani, D. I. Ketcheson, W. Deconinck,  Optimized explicit Runge–Kutta schemes for the spectral difference method applied to wave propagation problems,  SIAM Journal on Scientific Computing 35 (2013) A957–A986. doi:10.1137/120885899.
  * Kennedy et al. [2000] C. A. Kennedy, M. H. Carpenter, R. M. Lewis,  Low-storage, explicit Runge–Kutta schemes for the compressible Navier–Stokes equations,  Applied Numerical Mathematics 35 (2000) 177–219. doi:10.1016/S0168-9274(99)00141-5.
  * Ranocha et al. [2022] H. Ranocha, L. Dalcin, M. Parsani, D. I. Ketcheson,  Optimized Runge-Kutta methods with automatic step size control for compressible computational fluid dynamics,  Communications on Applied Mathematics and Computation 4 (2022) 1191–1228. doi:10.1007/s42967-021-00159-w.
  * Bassi and Rebay [1997] F. Bassi, S. Rebay,  A high-order accurate discontinuous finite element method for the numerical solution of the compressible Navier–Stokes equations,  Journal of Computational Physics 131 (1997) 267–279. doi:10.1006/jcph.1996.5572.
  * Brown and Minion [1995] D. L. Brown, M. L. Minion,  Performance of under-resolved two-dimensional incompressible flow simulations,  Journal of Computational Physics 122 (1995) 165–183. doi:10.1006/jcph.1995.1205.
  * Ranocha [2018] H. Ranocha,  Comparison of some entropy conservative numerical fluxes for the Euler equations,  Journal of Scientific Computing 76 (2018) 216–242. doi:10.1007/s10915-017-0618-1.
  * Löhner [1987] R. Löhner,  An adaptive finite element scheme for transient problems in CFD,  Computer Methods in Applied Mechanics and Engineering 61 (1987) 323–338. doi:10.1016/0045-7825(87)90098-3.
  * Fryxell et al. [2000] B. Fryxell, K. Olson, P. Ricker, F. Timmes, M. Zingale, D. Lamb, P. MacNeice, R. Rosner, J. Truran, H. Tufo,  FLASH: An adaptive mesh hydrodynamics code for modeling astrophysical thermonuclear flashes,  The Astrophysical Journal Supplement Series 131 (2000) 273. doi:10.1086/317361.
  * Orszag and Tang [1979] S. A. Orszag, C.-M. Tang,  Small-scale structure of two-dimensional magnetohydrodynamic turbulence,  Journal of Fluid Mechanics 90 (1979) 129–143. doi:10.1017/S002211207900210X.
  * Warburton and Karniadakis [1999] T. Warburton, G. E. Karniadakis,  A discontinuous Galerkin method for the viscous mhd equations,  Journal of computational Physics 152 (1999) 608–641. doi:10.1006/jcph.1999.6248.
  * Derigs et al. [2018] D. Derigs, A. R. Winters, G. J. Gassner, S. Walch, M. Bohm,  Ideal GLM-MHD: about the entropy consistent nine-wave magnetic field divergence diminishing ideal magnetohydrodynamics equations,  Journal of Computational Physics 364 (2018) 420–467. doi:10.1016/j.jcp.2018.03.002.
  * Munz et al. [2000] C.-D. Munz, P. Omnes, R. Schneider, E. Sonnendrücker, U. Voss,  Divergence correction techniques for Maxwell solvers based on a hyperbolic model,  Journal of Computational Physics 161 (2000) 484–511. doi:10.1006/jcph.2000.6507.
  * Bohm et al. [2020] M. Bohm, A. R. Winters, G. J. Gassner, D. Derigs, F. Hindenlang, J. Saur,  An entropy stable nodal discontinuous Galerkin method for the resistive MHD equations. Part I: Theory and numerical verification,  Journal of Computational Physics 422 (2020) 108076. doi:10.1016/j.jcp.2018.06.027.
  * Powell et al. [1999] K. G. Powell, P. L. Roe, T. J. Linde, T. I. Gombosi, D. L. De Zeeuw,  A solution-adaptive upwind scheme for ideal magnetohydrodynamics,  Journal of Computational Physics 154 (1999) 284–309. doi:10.1006/jcph.1999.6299.
  * DeBonis [2013] J. DeBonis,  Solutions of the Taylor-Green vortex problem using high-resolution explicit finite difference methods,  in: 51st AIAA aerospace sciences meeting including the new horizons forum and aerospace exposition, 2013, pp. 1–20. URL: https://arc.aiaa.org/doi/abs/10.2514/6.2013-382. doi:10.2514/6.2013-382. arXiv:https://arc.aiaa.org/doi/pdf/10.2514/6.2013-382.
  * Bull and Jameson [2014] J. R. Bull, A. Jameson,  Simulation of the compressible Taylor Green vortex using high-order flux reconstruction schemes,  in: 7th AIAA Theoretical Fluid Mechanics Conference, 2014, p. 3210. URL: https://arc.aiaa.org/doi/abs/10.2514/6.2014-3210. doi:10.2514/6.2014-3210. arXiv:https://arc.aiaa.org/doi/pdf/10.2514/6.2014-3210.
  * Jacobs et al. [2017] C. T. Jacobs, S. P. Jammy, N. D. Sandham,  Opensbli: A framework for the automated derivation and parallel execution of finite difference solvers on a range of computer architectures,  Journal of Computational Science 18 (2017) 12–23. doi:10.1016/j.jocs.2016.11.001.
  * Shi et al. [2003] J. Shi, Y.-T. Zhang, C.-W. Shu,  Resolution of high order WENO schemes for complicated flow structures,  Journal of Computational Physics 186 (2003) 690–696. doi:10.1016/S0021-9991(03)00094-9.
  * Derigs et al. [2018] D. Derigs, G. J. Gassner, S. Walch, A. R. Winters,  Entropy stable finite volume approximations for ideal magnetohydrodynamics,  Jahresbericht der Deutschen Mathematiker-Vereinigung 120 (2018) 153–219. doi:10.1365/s13291-018-0178-9.


# Searching k-Optimal Goals for an Orienteering Problem on a Specialized Graph
with Budget Constraints

Abhinav Sharma, Advait Deshpande, Yanming Wang, Xinyi Xu, Prashan Madumal,
Anbin Hou

###### Abstract

We propose a novel non-randomized anytime orienteering algorithm for finding
k-optimal goals that maximize reward on a specialized graph with budget
constraints. This specialized graph represents a real-world scenario which is
analogous to an orienteering problem of finding k-most optimal goal states.

## Introduction

Orienteering Problem (OP) is a special case of the Informative Path Planning
(IPP) problem where rewards at different nodes are calculated independently of
each other. However, the OP is considered to be NP-hard and mostly solved with
heuristic-based search strategies and customized algorithms (Wei and Zheng
2020). We aim to solve a domain-related orienteering problem which can be
formalized for a specialized directed weighted graph. First, we initialize a
specialized graph for mapping the Parkville campus of the University of
Melbourne. We then use this graph to formalize our problem of finding the most
optimal nearest building from a starting building such that the reward can be
maximized within the provided travelling budget constraint. The proposed non-
randomized algorithm is applied to find k-most optimal nearest buildings
inside the campus from a given starting building, discussed in the results
section. We also show how COVID-19 lock-down restrictions can be incorporated
into our algorithm to solve our defined orienteering problem.

## Problem Formulation

We formulate our domain-related optimal building finding problem into a
generic orienteering problem (OP) for a specialized graph below.

Let us assume a weighted directed specialized graph $G_{s}=(V,E)$ for $n$
number of nodes where $v_{s}\in V$ is the pre-defined start node such that
$V=\\{v_{1},v_{2},v_{3},...,v_{n}\\}$ and
$E=\\{(v_{s},v_{i})\>\backslash\>(v_{s},v_{s})\>|\>\forall\>i\in[1,n]\>\\}$.
Here, $v_{s}$ is having $n$ out-degree with 0 in-degree (i.e. $v_{s}$ is
connected to every other node in $V$) and $v_{i}\>\forall\>i\in[1,n]$
\$\>v_{s}$ is connected to only $v_{s}$ with 1 in-degree and 0 out-degree.

Let $v_{g}$ be the set of $k$-optimal goal nodes s.t. $v_{g}\in V$ and $k\leq
n$. These goals are attained in the decreasing order of their gained rewards
after respecting budget constraints (i.e. $v_{g1}>v_{g2}>...>v_{gk}$). Let $r$
be the set of nodes which we can visit such that $r\subseteq V$ \ $v_{s}$. Let
$B$ be the travelling budget which will enable the budget constraints. Let $O$
be the generic objectives and $F$ be the generic factors which can be used to
tweak the reward function of the problem.

For each $r$, let $R(r,o,f)$ be the reward function where
$\>R:(r,o,f)\rightarrow{\rm I\\!R}_{0}^{+}\cup\\{\infty\\}$ calculates the
reward based on the provided set of factors $f\subseteq F$ and objective $o\in
O$. Let $I(r)=R(r,o,f)$ be the reward gained by visiting each node in $r$. Let
the cost of traversal be given by $C(r)=C(v_{s},v_{i}^{r})$, where $v_{i}$ is
the $i^{th}$ element in $r$, $\forall i\in[1,|r|]$. Let $L\in{\rm
I\\!R}_{0}^{+}\cup\\{\infty\\}$ be the constraint limit. Using above
notations, the hard-constraint problem can then be defined by equation 1.

$\operatorname*{arg\,max}_{r\subseteq V}I(r)\>\textit{subject to}\>C(r)\leq
B\leq L$ (1)

We can relax the above hard-constraint by introducing a hyper-parameter
$\delta$ to formulate a soft-constraint problem as shown in equation 2.

$\operatorname*{arg\,max}_{r\subseteq V}I(r)\>\textit{subject to}\>C(r)\leq
B+\delta\leq L$ (2)

where $\delta\in{\rm I\\!R}_{0}^{+}\cup\\{\infty\\}$.

Informally, the solution to our stated problem is a set of ordered $k$-optimal
goal nodes, such that the reward obtained by visiting the node is maximized
while the path cost stays within a specified travelling budget $B$.

## Non-randomized Anytime Orienteering

In this section, we propose a novel way of solving the problem formulation
shown in equation 2 which is inspired by the general randomized algorithm for
IPP problems (Arora and Scherer 2017).

The algorithm starts with a priority queue and creates $r$ subset s.t.
$r\subseteq V$ \ $v_{s}$. Then, for each node in $r$, path cost $C(r)$ and
node reward $I(r)$ is calculated. It is then ensured that the budget
constraint is satisfied and the selected node is pushed into the priority
queue with negative reward as the priority. We can pop the queue item with
minimum priority $k$-times to find the $k$-most optimal goal nodes. This
process is described in Algorithm 1.

Inputs: $G_{s}=(V,E),v_{s},B,L,k,\delta$, $o\in O$, $f\subseteq F$

Output: $v_{g}=\\{v_{g1},..,v_{gk}\\}$ s.t. $v_{g1}>...>v_{gk}$

queue := new priority queue

$v_{g}=\emptyset$

$r:=r\subseteq V$ \ $v_{s}$

for  _$v_{i}\ >\>in\>\>r$_ do

$I(r)=R(v_{i},o,f)$ //node reward

$C(r)=C(v_{s},v_{i})$ //path cost

if  _$C(r)\leq B+\delta\leq L$_ then

$priority=-1*I(r)$

queue.insert($v_{i},priority$)

end if

end for

while  _not queue.empty()_ do

$\rho$ := queue.pop-min() //best node

if  _$len(v_{g}) <k$_ then

$v_{g}:=v_{g}\cup\rho$

end if

end while

Algorithm 1 Non-Randomized Anytime Orienteering to find k-optimal goals for a
specialized graph

### Time Complexity.

If we assume a standard binary heap implementation of the priority queue, then
the insertion and deletion time complexity is $O(log\>n)$, where $n$ is the
size of the input (Atkinson et al. 1986). This can be further optimized by
several customizations (Edelkamp, Elmasry, and Katajainen 2017). Hence, the
time complexity of our proposed algorithm for the best and the worst case can
be stated as $O(n-1\>*\>log\>n)+O(k\>*\>log\>n)\leq O(n\>log\>n)$.

### Space Complexity.

If we again assume a heap data structure implementation of the priority queue,
then the space complexity of storing $n$ elements in the priority queue is
$O(n)$ (Atkinson et al. 1986). Hence, the best and worst case space complexity
of our proposed algorithm is $O(n)$.

### Limitations.

Our algorithm relies on the assumption that the graph is a specialized
weighted directed graph with one central node (0 in-degree and $n$ out-degree)
and $n$ isolated nodes connected with only one central node. Due to this
assumption, the algorithm is efficient and applicable only for such versions
of the specialized graph and cannot be extended implicitly to any general
weighted directed graph.

## Experimental Results

In this section, we show experimental results for a domain-specific
orienteering problem solved using our proposed algorithm. Here, our goal is to
find the k-most optimal nearest building inside the Parkville campus of the
University of Melbourne. These buildings should be within a specific radius
($B$) that maximises the chances (reward) of either booking a meeting room or
using a toilet facility based on supply, demand and other preferences or
factors. A specific scenario is shown in Figure 1 where $R(.)$ are the rewards
given by the buildings with no factors and $R(\textit{COVID})$ are the rewards
based on COVID-19 lock-down restrictions.

Figure 1: Finding $k=3$ most optimal nearest building from $v_{s}=220$ that
maximises the chances (reward) of booking a meeting room within $B=200$ meters
and $\delta=50$ meters

Table 1 shows the results for the stated scenario for 3-optimal nearest
buildings using our proposed algorithm. In addition, we were also able to
simulate a COVID-19 restriction scenario by enhancing the reward function
$R(r,o,f)$, obtaining results as shown in the Table 2.

Goals | Cost | $R(.)$
---|---|---
$v_{g1}=260$ | 77.69 | 0.0020
$v_{g2}=204$ | 70.25 | 0.0014
$v_{g3}=104$ | 70.64 | 0.0007
Goals | Cost | $R(.)$
---|---|---
$v_{g1}=102$ | 246.39 | 0.0034
$v_{g2}=260$ | 77.69 | 0.0020
$v_{g3}=204$ | 70.25 | 0.0014

Table 1: $k=3$ most optimal nearest buildings without any factors with
$B=200\>m$ hard-constraint (left) and $B+\delta=250\>m$ soft-constraint
(right)

Goals | Cost | $R(\textit{COVID})$
---|---|---
$v_{g1}=110$ | 124.13 | 126
$v_{g2}=105$ | 130.83 | 111
$v_{g3}=104$ | 70.64 | 93
Goals | Cost | $R(\textit{COVID})$
---|---|---
$v_{g1}=110$ | 124.13 | 126
$v_{g2}=102$ | 246.39 | 117
$v_{g3}=105$ | 130.83 | 111

Table 2: $k=3$ most optimal nearest buildings in COVID lockdown situation with
$B=200\>m$ hard-constraint (left) and $B+\delta=250\>m$ soft-constraint
(right)

## References

  * Arora and Scherer (2017) Arora, S.; and Scherer, S. 2017.  Randomized algorithm for informative path planning with budget constraints.  In _2017 IEEE International Conference on Robotics and Automation (ICRA)_ , 4997–5004.
  * Atkinson et al. (1986) Atkinson, M. D.; Sack, J.-R.; Santoro, N.; and Strothotte, T. 1986.  Min-Max Heaps and Generalized Priority Queues.  _Commun. ACM_ 29(10): 996–1000.  ISSN 0001-0782.  doi:10.1145/6617.6621.  URL https://doi.org/10.1145/6617.6621.
  * Edelkamp, Elmasry, and Katajainen (2017) Edelkamp, S.; Elmasry, A.; and Katajainen, J. 2017.  Optimizing Binary Heaps.  _Theory of Computing Systems_ 61\.  doi:10.1007/s00224-017-9760-2.
  * Wei and Zheng (2020) Wei, Y.; and Zheng, R. 2020.  Informative Path Planning for Mobile Sensing with Reinforcement Learning.  doi:10.1109/INFOCOM41043.2020.9155528.