Search

In this paper, we consider an approach to improve the performance of exponential Runge–Kutta integrators and Lawson schemes in cases where the solution of a related, but usually much simpler, problem can be computed efficiently. While for implicit methods such an approach is common (e.g., by using preconditioners), for exponential integrators this has proven more challenging. Here we propose to extract a constant coefficient differential operator from the semilinear advection-diffusion-reaction equation for which, in many situations, efficient methods are known to compute the required matrix functions. Both a linear stability analysis and extensive numerical experiments show that the resulting schemes can be unconditionally stable. In fact, we find that exponential integrators of Runge–Kutta type and Lawson schemes can have better stability properties than similarly constructed implicit-explicit schemes. We also derive two new Lawson-type integrators that further improve on these stability properties. The overall effectiveness of the approach is highlighted by a number of performance comparisons on examples in two and three space dimensions. [ABSTRACT FROM AUTHOR]

This paper proposes a sketching strategy with spherical designs to equip the classical spherical basis function (SBF) approach for massive spherical data fitting. We conduct theoretical analysis and numerical verifications to demonstrate the feasibility of the proposed sketching strategy. From the theoretical side, we prove that sketching based on spherical designs can reduce the computational burden of the SBF approach without sacrificing its approximation capability. In particular, we provide upper and lower bounds for the proposed sketching strategy to fit noisy data on spheres. From the experimental side, we numerically illustrate the feasibility of the sketching strategy by showing its comparable fitting performance with the SBF approach. These interesting findings show that the proposed sketching strategy is effective in fitting massive and noisy data on spheres. [ABSTRACT FROM AUTHOR]

We analyze the recently introduced family of preconditioners in [M. M. Rana et al., SIAM J. Sci. Comput., 43 (2021), pp. S475-S495] for the stage equations of implicit Runge--Kutta methods for s-stage methods. We simplify the formulas for the eigenvalues and eigenvectors of the preconditioned systems for a general s-stage method and use these to obtain convergence rate estimates for preconditioned GMRES for some common choices of the implicit Runge-Kutta methods. This analysis is based on understanding the inherent matrix structure of these problems and exploiting it to qualitatively predict and explain the main observed features of the GMRES convergence behavior, using tools from approximation and potential theory based on Schwarz--Christoffel maps for curves and close, connected domains in the complex plane. We illustrate our analysis with numerical experiments showing very close correspondence of the estimates and the observed behavior, suggesting the analysis reliably captures the essence of these preconditioners. [ABSTRACT FROM AUTHOR]

Tensor wheel (TW) decomposition is an elegant compromise of the popular tensor ring decomposition and fully connected tensor network decomposition, and it has many applications. In this work, we investigate the computation of this decomposition. Three randomized algorithms based on random sampling or random projection are proposed. Specifically, by defining a new tensor product called the subwheel product, the structures of the coefficient matrices of the alternating least squares subproblems from the minimization problem of TW decomposition are first figured out. Then, using the structures and the properties of the subwheel product, a random sampling algorithm based on leverage sampling and two random projection algorithms respectively based on Kronecker subsampled randomized Fourier transform and TensorSketch are derived. These algorithms can implement the sampling and projection on TW factors and hence can avoid forming the full coefficient matrices of subproblems. We present the complexity analysis and numerical performance on synthetic data, real data, and image reconstruction for our algorithms. Experimental results show that, compared with the deterministic algorithm in the literature, they need much less computing time while achieving similar accuracy and reconstruction effect. We also apply the proposed algorithms to tensor completion and find that the sampling-based algorithm always has excellent performance and the projection-based algorithms behave well when the sampling rate is higher than 50%. [ABSTRACT FROM AUTHOR]

The multilevel Monte Carlo (MLMC) method is highly efficient for estimating expectations of a functional of a solution to a stochastic differential equation (SDE). However, MLMC estimators may be unstable and have a poor (noncanonical) complexity in the case of low regularity of the functional. To overcome this issue, we extend our previously introduced idea of numerical smoothing in [Quant. Finance, 23 (2023), pp. 209-227], in the context of deterministic quadrature methods to the MLMC setting. The numerical smoothing technique is based on root-finding methods combined with one-dimensional numerical integration with respect to a single well-chosen variable. This study is motivated by the computation of probabilities of events, pricing options with a discontinuous payoff, and density estimation problems for dynamics where the discretization of the underlying stochastic processes is necessary. The analysis and numerical experiments reveal that the numerical smoothing significantly improves the strong convergence and, consequently, the complexity and robustness (by making the kurtosis at deep levels bounded) of the MLMC method. In particular, we show that numerical smoothing enables recovering the MLMC complexities obtained for Lipschitz functionals due to the optimal variance decay rate when using the Euler--Maruyama scheme. For the Milstein scheme, numerical smoothing recovers the canonical MLMC complexity, even for the nonsmooth integrand mentioned above. Finally, our approach efficiently estimates univariate and multivariate density functions. [ABSTRACT FROM AUTHOR]

We study the learning of numerical algorithms for scientific computing, which combines mathematically driven, handcrafted design of general algorithm structure with a data-driven adaptation to specific classes of tasks. This represents a departure from the classical approaches in numerical analysis, which typically do not feature such learning-based adaptations. As a case study, we develop a machine learning approach that automatically learns effective solvers for initial value problems in the form of ordinary differential equations (ODEs), based on the Runge--Kutta (RK) integrator architecture. We show that we can learn high-order integrators for targeted families of differential equations without the need for computing integrator coefficients by hand. Moreover, we demonstrate that in certain cases we can obtain superior performance to classical RK methods. This can be attributed to certain properties of the ODE families being identified and exploited by the approach. Overall, this work demonstrates an effective learning-based approach to the design of algorithms for the numerical solution of differential equations. This can be readily extended to other numerical tasks. [ABSTRACT FROM AUTHOR]

We develop a novel computational framework to approximate solution operators of evolution partial differential equations (PDEs). By employing a general nonlinear reduced-order model, such as a deep neural network, to approximate the solution of a given PDE, we realize that the evolution of the model parameters is a control problem in the parameter space. Based on this observation, we propose to approximate the solution operator of the PDE by learning the control vector field in the parameter space. From any initial value, this control field can steer the parameter to generate a trajectory such that the corresponding reduced-order model solves the PDE. This allows for substantially reduced computational cost to solve the evolution PDE with arbitrary initial conditions. We also develop comprehensive error analysis for the proposed method when solving a large class of semilinear parabolic PDEs. Numerical experiments on different high-dimensional evolution PDEs with various initial conditions demonstrate the promising results of the proposed method. [ABSTRACT FROM AUTHOR]

Kinetic equations model the position-velocity distribution of particles subject to transport and collision effects. Under a diffusive scaling, these combined effects converge to a diffusion equation for the position density in the limit of an infinite collision rate. Despite this well-defined limit, numerical simulation is expensive when the collision rate is high but finite, as small time steps are then required. In this work, we present an asymptotic-preserving multilevel Monte Carlo particle scheme that makes use of this diffusive limit to accelerate computations. In this scheme, we first sample the diffusive limiting model to compute a biased initial estimate of a quantity of interest, using large time steps. We then perform a limited number of finer simulations with transport and collision dynamics to correct the bias. The efficiency of the multilevel method depends on being able to perform correlated simulations of particles on a hierarchy of discretization levels. We present a method for correlating particle trajectories and present both an analysis and numerical experiments. We demonstrate that our approach significantly reduces the cost of particle simulations in highcollisional regimes, compared with prior work, indicating significant potential for adopting these schemes in various areas of active research. [ABSTRACT FROM AUTHOR]

We provide a numerical platform for the analysis of particle shape and topology effect on the macroscopic behavior of granular media. We work within a discrete element method (DEM) framework and apply a peridynamic model for deformable particles accounting for deformation and damage of individual particles. To accommodate arbitrary particle shapes including nonconvex ones as well as particle topology, an efficient method is developed to keep intraparticle peridynamic interaction within particle boundaries. Particle contact with the rigid boundary wall is computed analytically to improve accuracy. To speed up simulations with particles of different shapes and sizes the initial configuration is chosen using security disks containing different particle shapes that are placed in a jammed state using an optimization-based method. The effect of particle shape and topology on settling and compaction of the aggregate for deformable particles is analyzed. [ABSTRACT FROM AUTHOR]

Our aim is the development and analysis of the numerical schemes for approximately solving the backward diffusion-wave problem, which involves a fractional derivative in time with order α ∈ (1,2). From terminal observations at two time levels, i.e., u(T1) and u(T2), we simultaneously recover two initial data u(0) and ut(0) and hence the solution u(t) for all t > 0. First, existence, uniqueness, and Lipschitz stability of the backward diffusion-wave problem were established under some conditions about T1 and T2. Moreover, for noisy data, we propose a quasi-boundary value scheme to regularize the "mildly" ill-posed problem, and show the convergence of the regularized solution. Next, to numerically solve the regularized problem, a fully discrete scheme is proposed by applying the finite element method in space and convolution quadrature in time. We establish error bounds of discrete solutions in both cases of smooth and nonsmooth data. Those estimates are very useful in practice since they indicate the ways to choose discretization parameters and regularization parameter, according to the noise level. Intensive numerical experiments show the accuracy of the numerical scheme and support our theoretical results. [ABSTRACT FROM AUTHOR]

This work is dedicated to the construction and analysis of high-order transparent boundary conditions for the weighted wave equation on a fractal tree, which models sound propagation inside human lungs. This article follows the works [P. Joly, M. Kachanovska and A. Semin, Netw. Heterog. Media, 14 (2019), pp. 205–264; P. Joly and M. Kachanovska, Numer. Math., 146 (2020), pp. 281–334], aimed at the analysis and numerical treatment of the model, as well as the construction of low-order and exact discrete boundary conditions. The method suggested in the present work is based on the truncation of the meromorphic series that represents the symbol of the Dirichlet-to-Neumann operator, in the spirit of the absorbing boundary conditions of Engquist and Majda. We analyze its stability and convergence, as well as present computational aspects of the method. Numerical results confirm theoretical findings. [ABSTRACT FROM AUTHOR]

We present a fast and approximate multifrontal solver for large-scale sparse linear systems arising from finite-difference, finite-volume, or finite-element discretization of high-frequency wave equations. The proposed solver leverages the butterfly algorithm and its hierarchical matrix extension for compressing and factorizing large frontal matrices via graph distance guided entry evaluation or randomized matrix-vector multiplication-based schemes. Complexity analysis and numerical experiments demonstrate O (N log² N) computation and O (N) memory complexity when applied to an N X N sparse system arising from 3D high-frequency Helmholtz and Maxwell problems. [ABSTRACT FROM AUTHOR]