Numerical Analysis

New submissions

• New submissions
• Cross-lists
• Replacements

New submissions for Fri, 24 May 24

[1]  arXiv:2405.13269 [pdf, other]

Title: Analysis of reconstruction from noisy discrete generalized Radon data

Authors: Alexander Katsevich

Subjects: Numerical Analysis (math.NA); Probability (math.PR)

We consider a wide class of generalized Radon transforms $\mathcal R$, which act in $\mathbb{R}^n$ for any $n\ge 2$ and integrate over submanifolds of any codimension $N$, $1\le N\le n-1$. Also, we allow for a fairly general reconstruction operator $\mathcal A$. The main requirement is that $\mathcal A$ be a Fourier integral operator with a phase function, which is linear in the phase variable. We consider the task of image reconstruction from discrete data $g_{j,k} = (\mathcal R f)_{j,k} + \eta_{j,k}$. We show that the reconstruction error $N_\epsilon^{\text{rec}}=\mathcal A \eta_{j,k}$ satisfies $N^{\text{rec}}(\check x;x_0)=\lim_{\epsilon\to0}N_\epsilon^{\text{rec}}(x_0+\epsilon\check x)$, $\check x\in D$. Here $x_0$ is a fixed point, $D\subset\mathbb{R}^n$ is a bounded domain, and $\eta_{j,k}$ are independent, but not necessarily identically distributed, random variables. $N^{\text{rec}}$ and $N_\epsilon^{\text{rec}}$ are viewed as continuous random functions of the argument $\check x$ (random fields), and the limit is understood in the sense of probability distributions. Under some conditions on the first three moments of $\eta_{j,k}$ (and some other not very restrictive conditions on $x_0$ and $\mathcal A$), we prove that $N^{\text{rec}}$ is a zero mean Gaussian random field and explicitly compute its covariance. We also present a numerical experiment with a cone beam transform in $\mathbb{R}^3$, which shows an excellent match between theoretical predictions and simulated reconstructions.

[2]  arXiv:2405.13340 [pdf, other]

Title: Randomized block coordinate descent method for linear ill-posed problems

Authors: Qinian Jin, Duo Liu

Subjects: Numerical Analysis (math.NA); Optimization and Control (math.OC)

Consider the linear ill-posed problems of the form $\sum_{i=1}^{b} A_i x_i =y$, where, for each $i$, $A_i$ is a bounded linear operator between two Hilbert spaces $X_i$ and ${\mathcal Y}$. When $b$ is huge, solving the problem by an iterative method using the full gradient at each iteration step is both time-consuming and memory insufficient. Although randomized block coordinate decent (RBCD) method has been shown to be an efficient method for well-posed large-scale optimization problems with a small amount of memory, there still lacks a convergence analysis on the RBCD method for solving ill-posed problems. In this paper, we investigate the convergence property of the RBCD method with noisy data under either {\it a priori} or {\it a posteriori} stopping rules. We prove that the RBCD method combined with an {\it a priori} stopping rule yields a sequence that converges weakly to a solution of the problem almost surely. We also consider the early stopping of the RBCD method and demonstrate that the discrepancy principle can terminate the iteration after finite many steps almost surely. For a class of ill-posed problems with special tensor product form, we obtain strong convergence results on the RBCD method. Furthermore, we consider incorporating the convex regularization terms into the RBCD method to enhance the detection of solution features. To illustrate the theory and the performance of the method, numerical simulations from the imaging modalities in computed tomography and compressive temporal imaging are reported.

[3]  arXiv:2405.13423 [pdf, ps, other]

Title: A weak Galerkin finite element method for solving the asymptotic lower bound of Maxwell eigenvalue problem

Authors: Shusheng Li, Qilong Zhai

Subjects: Numerical Analysis (math.NA)

In this paper, we propose a weak Galerkin (WG) finite element method for the Maxwell eigenvalue problem. By restricting subspaces, we transform the mixed form of Maxwell eigenvalue problem into simple elliptic equation. Then we give the WG numerical scheme for the Maxwell eigenvalue problem. Furthermore, we obtain the optimal error estimates of arbitrarily high convergence order and prove the lower bound property of numerical solutions for eigenvalues. Numerical experiments show the accuracy of theoretical analysis and the property of lower bound.

[4]  arXiv:2405.13430 [pdf, ps, other]

Title: The Unisolvence of Lagrange Interpolation with Symmetric Interpolation Space and Nodes in High Dimension

Authors: Yulin Xie, Yifa Tang

Comments: 18 pages

Subjects: Numerical Analysis (math.NA)

High-dimensional Lagrange interpolation plays a pivotal role in finite element methods, where ensuring the unisolvence and symmetry of its interpolation space and nodes set is crucial. In this paper, we leverage group action and group representation theories to precisely delineate the conditions for unisolvence. We establish a necessary condition for unisolvence: the symmetry of the interpolation nodes set is determined by the given interpolation space. Our findings not only contribute to a deeper theoretical understanding but also promise practical benefits by reducing the computational overhead associated with identifying appropriate interpolation nodes.

[5]  arXiv:2405.13441 [pdf, ps, other]

Title: An all Mach number semi-implicit hybrid Finite Volume/Virtual Element method for compressible viscous flows on Voronoi meshes

Authors: Walter Boscheri, Saray Busto, Michael Dumbser

Subjects: Numerical Analysis (math.NA); Fluid Dynamics (physics.flu-dyn)

We present a novel high order semi-implicit hybrid finite volume/virtual element numerical scheme for the solution of compressible flows on Voronoi tessellations. The method relies on the flux splitting of the compressible Navier-Stokes equations into three sub-systems: a convective sub-system solved explicitly using a finite volume (FV) scheme, and the viscous and pressure sub-systems which are discretized implicitly at the aid of a virtual element method (VEM). Consequently, the time step restriction of the overall algorithm depends only on the mean flow velocity and not on the fast pressure waves nor on the viscous eigenvalues. As such, the proposed methodology is well suited for the solution of low Mach number flows at all Reynolds numbers. Moreover, the scheme is proven to be globally energy conserving so that shock capturing properties are retrieved in high Mach number flows. To reach high order of accuracy in time and space, an IMEX Runge-Kutta time stepping strategy is employed together with high order spatial reconstructions in terms of CWENO polynomials and virtual element space basis functions. The chosen discretization techniques allow the use of general polygonal grids, a useful tool when dealing with complex domain configurations. The new scheme is carefully validated in both the incompressible limit and the high Mach number regime through a large set of classical benchmarks for fluid dynamics, assessing robustness and accuracy.

[6]  arXiv:2405.13520 [pdf, other]

Title: Network Inpainting via Optimal Transport

Authors: Enrico Facca, Jan Martin Nordbotten, Erik Andreas Hanson

Subjects: Numerical Analysis (math.NA); Optimization and Control (math.OC)

In this work, we present a novel tool for reconstructing networks from corrupted images. The reconstructed network is the result of a minimization problem that has a misfit term with respect to the observed data, and a physics-based regularizing term coming from the theory of optimal transport. Through a range of numerical tests, we demonstrate that our suggested approach can effectively rebuild the primary features of damaged networks, even when artifacts are present.

[7]  arXiv:2405.13566 [pdf, ps, other]

Title: Bounds on the approximation error for deep neural networks applied to dispersive models: Nonlinear waves

Authors: Claudio Muñoz, Nicolás Valenzuela

Comments: 50 pp

Subjects: Numerical Analysis (math.NA); Analysis of PDEs (math.AP); Probability (math.PR)

We present a comprehensive framework for deriving rigorous and efficient bounds on the approximation error of deep neural networks in PDE models characterized by branching mechanisms, such as waves, Schr\"odinger equations, and other dispersive models. This framework utilizes the probabilistic setting established by Henry-Labord\`ere and Touzi. We illustrate this approach by providing rigorous bounds on the approximation error for both linear and nonlinear waves in physical dimensions $d=1,2,3$, and analyze their respective computational costs starting from time zero. We investigate two key scenarios: one involving a linear perturbative source term, and another focusing on pure nonlinear internal interactions.

[8]  arXiv:2405.13649 [pdf, other]

Title: The Jacobi Eigenvalue Algorithm for Computing the Eigenvalues of a Dual Quaternion Hermitian Matrix

Authors: Yongjun Chen, Liping Zhang

Subjects: Numerical Analysis (math.NA)

In this paper, we generalize the Jacobi eigenvalue algorithm to compute all eigenvalues and eigenvectors of a dual quaternion Hermitian matrix and show the convergence. We also propose a three-step Jacobi eigenvalue algorithm to compute the eigenvalues when a dual quaternion Hermitian matrix has two eigenvalues with identical standard parts but different dual parts and prove the convergence. Numerical experiments are presented to illustrate the efficiency and stability of the proposed Jacobi eigenvalue algorithm compaired to the power method and the Rayleigh quotient iteration method.

[9]  arXiv:2405.13657 [pdf, ps, other]

Title: A Conforming virtual element approximation for the Oseen eigenvalue problem

Authors: Danilo Amigo, Felipe Lepe, Nitesh Verma

Subjects: Numerical Analysis (math.NA)

In this paper we analyze a conforming virtual element method to approximate the eigenfunctions and eigenvalues of the two dimensional Oseen eigenvalue problem. We consider the classic velocity-pressure formulation which allows us to consider the divergence-conforming virtual element spaces employed for the Stokes equations. Under standard assumptions on the meshes we derive a priori error estimates for the proposed method with the aid of the compact operators theory. We report some numerical tests to confirm the theoretical results.

[10]  arXiv:2405.13921 [pdf, ps, other]

Title: Algebraic Conditions for Stability in Runge-Kutta Methods and Their Certification via Semidefinite Programming

Authors: Austin Juhl, David Shirokoff

Comments: 30 pages, 1 figure

Subjects: Numerical Analysis (math.NA); Optimization and Control (math.OC)

In this work, we present approaches to rigorously certify $A$- and $A(\alpha)$-stability in Runge-Kutta methods through the solution of convex feasibility problems defined by linear matrix inequalities. We adopt two approaches. The first is based on sum-of-squares programming applied to the Runge-Kutta $E$-polynomial and is applicable to both $A$- and $A(\alpha)$-stability. In the second, we sharpen the algebraic conditions for $A$-stability of Cooper, Scherer, T{\"u}rke, and Wendler to incorporate the Runge-Kutta order conditions. We demonstrate how the theoretical improvement enables the practical use of these conditions for certification of $A$-stability within a computational framework. We then use both approaches to obtain rigorous certificates of stability for several diagonally implicit schemes devised in the literature.

[11]  arXiv:2405.13936 [pdf, other]

Title: Nonisothermal Cahn-Hilliard Navier-Stokes system

Authors: Aaron Brunk, Dennis Schumann

Comments: 8 pages; 8 figures; 1 table

Subjects: Numerical Analysis (math.NA)

In this research, we introduce and investigate an approximation method that preserves the structural integrity of the non-isothermal Cahn-Hilliard-Navier-Stokes system. Our approach extends a previously proposed technique [1], which utilizes conforming (inf-sup stable) finite elements in space, coupled with implicit time discretization employing convex-concave splitting. Expanding upon this method, we incorporate the unstable P1|P1 pair for the Navier-Stokes contributions, integrating Brezzi-Pitk\"aranta stabilization. Additionally, we improve the enforcement of incompressibility conditions through grad div stabilization. While these techniques are well-established for Navier-Stokes equations, it becomes apparent that for non-isothermal models, they introduce additional coupling terms to the equation governing internal energy. To ensure the conservation of total energy and maintain entropy production, these stabilization terms are appropriately integrated into the internal energy equation.

[12]  arXiv:2405.13986 [pdf, other]

Title: High order finite-difference ghost-point methods for elliptic problems in domains with curved boundaries

Authors: Armando Coco, Giovanni Russo

Subjects: Numerical Analysis (math.NA)

In this paper a fourth order finite difference ghost point method for the Poisson equation on regular Cartesian mesh is presented. The method can be considered the high order extension of the second ghost method introduced earlier by the authors. Three different discretizations are considered, which differ in the stencil that discretizes the Laplacian and the source term. It is shown that only two of them provide a stable method. The accuracy of such stable methods are numerically verified on several test problems.

[13]  arXiv:2405.14110 [pdf, other]

Title: Regularity-Conforming Neural Networks (ReCoNNs) for solving Partial Differential Equations

Authors: Jamie M. Taylor, David Pardo, Judit Muñoz-Matute

Subjects: Numerical Analysis (math.NA)

Whilst the Universal Approximation Theorem guarantees the existence of approximations to Sobolev functions -- the natural function spaces for PDEs -- by Neural Networks (NNs) of sufficient size, low-regularity solutions may lead to poor approximations in practice. For example, classical fully-connected feed-forward NNs fail to approximate continuous functions whose gradient is discontinuous when employing strong formulations like in Physics Informed Neural Networks (PINNs). In this article, we propose the use of regularity-conforming neural networks, where a priori information on the regularity of solutions to PDEs can be employed to construct proper architectures. We illustrate the potential of such architectures via a two-dimensional (2D) transmission problem, where the solution may admit discontinuities in the gradient across interfaces, as well as power-like singularities at certain points. In particular, we formulate the weak transmission problem in a PINNs-like strong formulation with interface and continuity conditions. Such architectures are partially explainable; discontinuities are explicitly described, allowing the introduction of novel terms into the loss function. We demonstrate via several model problems in one and two dimensions the advantages of using regularity-conforming architectures in contrast to classical architectures. The ideas presented in this article easily extend to problems in higher dimensions.

[14]  arXiv:2405.14229 [pdf, other]

Title: Piecewise rational rotation-minimizing motions via data stream interpolation

Authors: Carlotta Giannelli, Lorenzo Sacco, Alessandra Sestioni, Zbyněk Šír

Comments: 29 pages, 14 figures

Subjects: Numerical Analysis (math.NA)

When a moving frame defined along a space curve is required to keep an axis aligned with the tangent direction of motion, the use of rotation-minimizing frames (RMF) avoids unnecessary rotations in the normal plane. The construction of rigid body motions using a specific subset of quintic curves with rational RMFs (RRMFs) is here considered. In particular, a novel geometric characterization of such subset enables the design of a local algorithm to interpolate an assigned stream of positions, together with an initial frame orientation. To achieve this, the translational part of the motion is described by a parametric $G^1$ spline curve whose segments are quintic RRMFs, with a globally continuous piecewise rational rotation-minimizing frame. A selection of numerical experiments illustrates the performances of the proposed method on synthetic and arbitrary data streams.

[15]  arXiv:2405.14408 [pdf, other]

Title: Adaptive tempering schedules with approximative intermediate measures for filtering problems

Authors: Iris Rammelmüller, Gottfried Hastermann, Jana de Wiljes

Subjects: Numerical Analysis (math.NA); Computation (stat.CO)

Data assimilation algorithms integrate prior information from numerical model simulations with observed data. Ensemble-based filters, regarded as state-of-the-art, are widely employed for large-scale estimation tasks in disciplines such as geoscience and meteorology. Despite their inability to produce the true posterior distribution for nonlinear systems, their robustness and capacity for state tracking are noteworthy. In contrast, Particle filters yield the correct distribution in the ensemble limit but require substantially larger ensemble sizes than ensemble-based filters to maintain stability in higher-dimensional spaces. It is essential to transcend traditional Gaussian assumptions to achieve realistic quantification of uncertainties. One approach involves the hybridisation of filters, facilitated by tempering, to harness the complementary strengths of different filters. A new adaptive tempering method is proposed to tune the underlying schedule, aiming to systematically surpass the performance previously achieved. Although promising numerical results for certain filter combinations in toy examples exist in the literature, the tuning of hyperparameters presents a considerable challenge. A deeper understanding of these interactions is crucial for practical applications.

[16]  arXiv:2405.14484 [pdf, ps, other]

Title: Novel semi-explicit symplectic schemes for nonseparable stochastic Hamiltonian systems

Authors: Jialin Hong, Baohui Hou, Liying Sun

Subjects: Numerical Analysis (math.NA)

In this manuscript, we propose efficient stochastic semi-explicit symplectic schemes tailored for nonseparable stochastic Hamiltonian systems (SHSs). These semi-explicit symplectic schemes are constructed by introducing augmented Hamiltonians and using symmetric projection. In the case of the artificial restraint in augmented Hamiltonians being zero, the proposed schemes also preserve quadratic invariants, making them suitable for developing semi-explicit charge-preserved multi-symplectic schemes for stochastic cubic Schr\"odinger equations with multiplicative noise. Through numerical experiments that validate theoretical results, we demonstrate that the proposed stochastic semi-explicit symplectic scheme, which features a straightforward Newton iteration solver, outperforms the traditional stochastic midpoint scheme in terms of effectiveness and accuracy.

[17]  arXiv:2405.14572 [pdf, other]

Title: Multicontinuum Homogenization for Coupled Flow and Transport Equations

Authors: Dmitry Ammosov, W. T. Leung, Buzheng Shan, Jian Huang

Subjects: Numerical Analysis (math.NA)

In this paper, we present the derivation of a multicontinuum model for the coupled flow and transport equations by applying multicontinuum homogenization. We perform the multicontinuum expansion for both flow and transport solutions and formulate novel coupled constraint cell problems to capture the multiscale property, where oversampled regions are utilized to avoid boundary effects. Assuming the smoothness of macroscopic variables, we obtain a multicontinuum system composed of macroscopic elliptic equations and convection-diffusion-reaction equations with homogenized effective properties. Finally, we present numerical results for various coefficient fields and boundary conditions to validate our proposed algorithm.

[18]  arXiv:2405.14605 [pdf, ps, other]

Title: Spectral analysis of block preconditioners for double saddle-point linear systems with application to PDE-constrained optimization

Authors: Luca Bergamaschi, Ángeles Martínez, John Pearson, Andreas Potschka

Subjects: Numerical Analysis (math.NA)

In this paper, we describe and analyze the spectral properties of a symmetric positive definite inexact block preconditioner for a class of symmetric, double saddle-point linear systems.
We develop a spectral analysis of the preconditioned matrix, showing that its eigenvalues can be described in terms of the roots of a cubic polynomial with real coefficients.
We illustrate the efficiency of the proposed preconditioners, and verify the theoretical bounds, in solving large-scale PDE-constrained optimization problems.

[19]  arXiv:2405.14763 [pdf, other]

Title: Structure preserving finite element schemes for the Navier-Stokes-Cahn-Hilliard system with degenerate mobility

Authors: Francisco Guillén-González, Giordano Tierra

Subjects: Numerical Analysis (math.NA)

In this work we present two new numerical schemes to approximate the Navier-Stokes-Cahn-Hilliard system with degenerate mobility using finite differences in time and finite elements in space. The proposed schemes are conservative, energy-stable and preserve the maximum principle approximately (the amount of the phase variable being outside of the interval [0,1] goes to zero in terms of a truncation parameter). Additionally, we present several numerical results to illustrate the accuracy and the well behavior of the proposed schemes, as well as a comparison with the behavior of the Navier-Stokes-Cahn-Hilliard model with constant mobility.

[20]  arXiv:2405.14772 [pdf, ps, other]

Title: Vortex-capturing multiscale spaces for the Ginzburg-Landau equation

Authors: Maria Blum, Christian Döding, Patrick Henning

Subjects: Numerical Analysis (math.NA)

This paper considers minimizers of the Ginzburg-Landau energy functional in particular multiscale spaces which are based on finite elements. The spaces are constructed by localized orthogonal decomposition techniques and their usage for solving the Ginzburg-Landau equation was first suggested in [D\"orich, Henning, SINUM 2024]. In this work we further explore their approximation properties and give an analytical explanation for why vortex structures of energy minimizers can be captured more accurately in these spaces. We quantify the necessary mesh resolution in terms of the Ginzburg-Landau parameter $\kappa$ and a stabilization parameter $\beta \ge 0$ that is used in the construction of the multiscale spaces. Furthermore, we analyze how $\kappa$ affects the necessary locality of the multiscale basis functions and we prove that the choice $\beta=0$ yields typically the highest accuracy. Our findings are supported by numerical experiments.

[21]  arXiv:2405.14849 [pdf, other]

Title: Novel $H^\mathrm{dev}(\mathrm{Curl})$-conforming elements on regular triangulations and Clough--Tocher splits for the planar relaxed micromorphic model

Authors: Adam Sky, Michael Neunteufel, Peter Lewintan, Panos Gourgiotis, Andreas Zilian, Patrizio Neff

Subjects: Numerical Analysis (math.NA)

In this work we present a consistent reduction of the relaxed micromorphic model to its corresponding two-dimensional planar model, such that its capacity to capture discontinuous dilatation fields is preserved. As a direct consequence of our approach, new conforming finite elements for $H^\mathrm{dev}(\mathrm{Curl},A)$ become necessary. We present two novel $H^\mathrm{dev}(\mathrm{Curl},A)$-conforming finite element spaces, of which one is a macro element based on Clough--Tocher splits, as well as primal and mixed variational formulations of the planar relaxed micromorphic model. Finally, we demonstrate the effectiveness of our approach with two numerical examples.

Cross-lists for Fri, 24 May 24

[22]  arXiv:2405.13149 (cross-list from stat.ML) [pdf, other]

Title: Gaussian Measures Conditioned on Nonlinear Observations: Consistency, MAP Estimators, and Simulation

Authors: Yifan Chen, Bamdad Hosseini, Houman Owhadi, Andrew M Stuart

Subjects: Machine Learning (stat.ML); Machine Learning (cs.LG); Numerical Analysis (math.NA); Probability (math.PR); Computation (stat.CO)

The article presents a systematic study of the problem of conditioning a Gaussian random variable $\xi$ on nonlinear observations of the form $F \circ \phi(\xi)$ where $\phi: \mathcal{X} \to \mathbb{R}^N$ is a bounded linear operator and $F$ is nonlinear. Such problems arise in the context of Bayesian inference and recent machine learning-inspired PDE solvers. We give a representer theorem for the conditioned random variable $\xi \mid F\circ \phi(\xi)$, stating that it decomposes as the sum of an infinite-dimensional Gaussian (which is identified analytically) as well as a finite-dimensional non-Gaussian measure. We also introduce a novel notion of the mode of a conditional measure by taking the limit of the natural relaxation of the problem, to which we can apply the existing notion of maximum a posteriori estimators of posterior measures. Finally, we introduce a variant of the Laplace approximation for the efficient simulation of the aforementioned conditioned Gaussian random variables towards uncertainty quantification.

[23]  arXiv:2405.13165 (cross-list from physics.flu-dyn) [pdf, other]

Title: Adaptive coupling of 3D and 2D fluid flow models

Authors: Pratik Suchde

Subjects: Fluid Dynamics (physics.flu-dyn); Numerical Analysis (math.NA)

Similar to the notion of h-adaptivity, where the discretization resolution is adaptively changed, I propose the notion of model adaptivity, where the underlying model (the governing equations) is adaptively changed in space and time. Specifically, this work introduces a hybrid and adaptive coupling of a 3D bulk fluid flow model with a 2D thin film flow model. As a result, this work extends the applicability of existing thin film flow models to complex scenarios where, for example, bulk flow develops into thin films after striking a surface. At each location in space and time, the proposed framework automatically decides whether a 3D model or a 2D model must be applied. Using a meshless approach for both 3D and 2D models, at each particle, the decision to apply a 2D or 3D model is based on the user-prescribed resolution and a local principal component analysis. When a particle needs to be changed from a 3D model to 2D, or vice versa, the discretization is changed, and all relevant data mapping is done on-the-fly. Appropriate two-way coupling conditions and mass conservation considerations between the 3D and 2D models are also developed. Numerical results show that this model adaptive framework shows higher flexibility and compares well against finely resolved 3D simulations. In an actual application scenario, a 3 factor speed up is obtained, while maintaining the accuracy of the solution.

[24]  arXiv:2405.13220 (cross-list from cs.LG) [pdf, other]

Title: Paired Autoencoders for Inverse Problems

Authors: Matthias Chung, Emma Hart, Julianne Chung, Bas Peters, Eldad Haber

Comments: 18 pages, 6 figures

Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Numerical Analysis (math.NA)

We consider the solution of nonlinear inverse problems where the forward problem is a discretization of a partial differential equation. Such problems are notoriously difficult to solve in practice and require minimizing a combination of a data-fit term and a regularization term. The main computational bottleneck of typical algorithms is the direct estimation of the data misfit. Therefore, likelihood-free approaches have become appealing alternatives. Nonetheless, difficulties in generalization and limitations in accuracy have hindered their broader utility and applicability. In this work, we use a paired autoencoder framework as a likelihood-free estimator for inverse problems. We show that the use of such an architecture allows us to construct a solution efficiently and to overcome some known open problems when using likelihood-free estimators. In particular, our framework can assess the quality of the solution and improve on it if needed. We demonstrate the viability of our approach using examples from full waveform inversion and inverse electromagnetic imaging.

[25]  arXiv:2405.13390 (cross-list from cs.LG) [pdf, ps, other]

Title: Convergence analysis of kernel learning FBSDE filter

Authors: Yunzheng Lyu, Feng Bao

Subjects: Machine Learning (cs.LG); Numerical Analysis (math.NA); Mathematical Finance (q-fin.MF)

Kernel learning forward backward SDE filter is an iterative and adaptive meshfree approach to solve the nonlinear filtering problem. It builds from forward backward SDE for Fokker-Planker equation, which defines evolving density for the state variable, and employs KDE to approximate density. This algorithm has shown more superior performance than mainstream particle filter method, in both convergence speed and efficiency of solving high dimension problems.
However, this method has only been shown to converge empirically. In this paper, we present a rigorous analysis to demonstrate its local and global convergence, and provide theoretical support for its empirical results.

[26]  arXiv:2405.13436 (cross-list from math.AP) [pdf, other]

Title: On the approximation of the von Neumann equation in the semi-classical limit. Part I : numerical algorithm

Authors: Francis Filbet (IMT), François Golse (CMLS)

Subjects: Analysis of PDEs (math.AP); Numerical Analysis (math.NA)

We propose a new approach to discretize the von Neumann equation, which is efficient in the semi-classical limit. This method is first based on the so called Weyl's variables to address the stiffness associated with the equation. Then, by applying a truncated Hermite expansion of the density operator, we successfully handle this stiffness. Additionally, we develop a finite volume approximation for practical implementation and conduct numerical simulations to illustrate the efficiency of our approach. This asymptotic preserving numerical approximation, combined with the use of Hermite polynomials, provides an efficient tool for solving the von Neumann equation in all regimes, near classical or not.

[27]  arXiv:2405.13458 (cross-list from math.FA) [pdf, ps, other]

Title: New Tight Wavelet Frame Constructions Sharing Responsibility

Authors: Youngmi Hur, Hyojae Lim

Subjects: Functional Analysis (math.FA); Numerical Analysis (math.NA)

Tight wavelet frames (TWFs) in $L^2(\mathbb{R}^n)$ are versatile and practical structures that provide the perfect reconstruction property. Nevertheless, existing TWF construction methods exhibit limitations, including a lack of specific methods for generating mother wavelets in extension-based construction, and the necessity to address the sum of squares (SOS) problem even when specific methods for generating mother wavelets are provided in SOS-based construction. It is a common practice for current TWF constructions to begin with a given refinable function. However, this approach places the entire burden on finding suitable mother wavelets. In this paper, we introduce TWF construction methods that spread the burden between both types of functions: refinable functions and mother wavelets. These construction methods offer an alternative approach to circumvent the SOS problem while providing specific techniques for generating mother wavelets. We present examples to illustrate our construction methods.

[28]  arXiv:2405.13691 (cross-list from physics.flu-dyn) [pdf, other]

Title: Neural Networks-based Random Vortex Methods for Modelling Incompressible Flows

Authors: Vladislav Cherepanov, Sebastian W. Ertel

Comments: 16 pages, 5 figures

Subjects: Fluid Dynamics (physics.flu-dyn); Numerical Analysis (math.NA); Probability (math.PR); Machine Learning (stat.ML)

In this paper we introduce a novel Neural Networks-based approach for approximating solutions to the (2D) incompressible Navier--Stokes equations. Our algorithm uses a Physics-informed Neural Network, that approximates the vorticity based on a loss function that uses a computationally efficient formulation of the Random Vortex dynamics. The neural vorticity estimator is then combined with traditional numerical PDE-solvers for the Poisson equation to compute the velocity field. The main advantage of our method compared to standard Physics-informed Neural Networks is that it strictly enforces physical properties, such as incompressibility or boundary conditions, which might otherwise be hard to guarantee with purely Neural Networks-based approaches.

[29]  arXiv:2405.13821 (cross-list from stat.CO) [pdf, other]

Title: Normalizing Basis Functions: Approximate Stationary Models for Large Spatial Data

Authors: Antony Sikorski, Daniel McKenzie, Douglas Nychka

Subjects: Computation (stat.CO); Numerical Analysis (math.NA); Applications (stat.AP)

In geostatistics, traditional spatial models often rely on the Gaussian Process (GP) to fit stationary covariances to data. It is well known that this approach becomes computationally infeasible when dealing with large data volumes, necessitating the use of approximate methods. A powerful class of methods approximate the GP as a sum of basis functions with random coefficients. Although this technique offers computational efficiency, it does not inherently guarantee a stationary covariance. To mitigate this issue, the basis functions can be "normalized" to maintain a constant marginal variance, avoiding unwanted artifacts and edge effects. This allows for the fitting of nearly stationary models to large, potentially non-stationary datasets, providing a rigorous base to extend to more complex problems. Unfortunately, the process of normalizing these basis functions is computationally demanding. To address this, we introduce two fast and accurate algorithms to the normalization step, allowing for efficient prediction on fine grids. The practical value of these algorithms is showcased in the context of a spatial analysis on a large dataset, where significant computational speedups are achieved. While implementation and testing are done specifically within the LatticeKrig framework, these algorithms can be adapted to other basis function methods operating on regular grids.

[30]  arXiv:2405.13938 (cross-list from cs.LG) [pdf, other]

Title: eXmY: A Data Type and Technique for Arbitrary Bit Precision Quantization

Authors: Aditya Agrawal, Matthew Hedlund, Blake Hechtman

Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Numerical Analysis (math.NA)

eXmY is a novel data type for quantization of ML models. It supports both arbitrary bit widths and arbitrary integer and floating point formats. For example, it seamlessly supports 3, 5, 6, 7, 9 bit formats. For a specific bit width, say 7, it defines all possible formats e.g. e0m6, e1m5, e2m4, e3m3, e4m2, e5m1 and e6m0. For non-power of two bit widths e.g. 5, 6, 7, we created a novel encoding and decoding scheme which achieves perfect compression, byte addressability and is amenable to sharding and vector processing. We implemented libraries for emulation, encoding and decoding tensors and checkpoints in C++, TensorFlow, JAX and PAX. For optimal performance, the codecs use SIMD instructions on CPUs and vector instructions on TPUs and GPUs. eXmY is also a technique and exploits the statistical distribution of exponents in tensors. It can be used to quantize weights, static and dynamic activations, gradients, master weights and optimizer state. It can reduce memory (CPU DRAM and accelerator HBM), network and disk storage and transfers. It can increase multi tenancy and accelerate compute. eXmY has been deployed in production for almost 2 years.

[31]  arXiv:2405.14096 (cross-list from cs.LG) [pdf, other]

Title: Newton Informed Neural Operator for Computing Multiple Solutions of Nonlinear Partials Differential Equations

Authors: Wenrui Hao, Xinliang Liu, Yahong Yang

Subjects: Machine Learning (cs.LG); Numerical Analysis (math.NA)

Solving nonlinear partial differential equations (PDEs) with multiple solutions using neural networks has found widespread applications in various fields such as physics, biology, and engineering. However, classical neural network methods for solving nonlinear PDEs, such as Physics-Informed Neural Networks (PINN), Deep Ritz methods, and DeepONet, often encounter challenges when confronted with the presence of multiple solutions inherent in the nonlinear problem. These methods may encounter ill-posedness issues. In this paper, we propose a novel approach called the Newton Informed Neural Operator, which builds upon existing neural network techniques to tackle nonlinearities. Our method combines classical Newton methods, addressing well-posed problems, and efficiently learns multiple solutions in a single learning process while requiring fewer supervised data points compared to existing neural network methods.

[32]  arXiv:2405.14098 (cross-list from math.OC) [pdf, ps, other]

Title: A continuous perspective on the inertial corrected primal-dual proximal splitting

Authors: Hao Luo

Subjects: Optimization and Control (math.OC); Numerical Analysis (math.NA)

We give a continuous perspective on the Inertial Corrected Primal-Dual Proximal Splitting (IC-PDPS) proposed by Valkonen ({\it SIAM J. Optim.}, 30(2): 1391--1420, 2020) for solving saddle-point problems. The algorithm possesses nonergodic convergence rate and admits a tight preconditioned proximal point formulation which involves both inertia and additional correction. Based on new understandings on the relation between the discrete step size and rescaling effect, we rebuild IC-PDPS as a semi-implicit Euler scheme with respect to its iterative sequences and integrated parameters. This leads to two novel second-order ordinary differential equation (ODE) models that are equivalent under proper time transformation, and also provides an alternative interpretation from the continuous point of view. Besides, we present the convergence analysis of the Lagrangian gap along the continuous trajectory by using proper Lyapunov functions.

[33]  arXiv:2405.14099 (cross-list from cs.LG) [pdf, other]

Title: Automatic Differentiation is Essential in Training Neural Networks for Solving Differential Equations

Authors: Chuqi Chen, Yahong Yang, Yang Xiang, Wenrui Hao

Subjects: Machine Learning (cs.LG); Numerical Analysis (math.NA)

Neural network-based approaches have recently shown significant promise in solving partial differential equations (PDEs) in science and engineering, especially in scenarios featuring complex domains or the incorporation of empirical data. One advantage of the neural network method for PDEs lies in its automatic differentiation (AD), which necessitates only the sample points themselves, unlike traditional finite difference (FD) approximations that require nearby local points to compute derivatives. In this paper, we quantitatively demonstrate the advantage of AD in training neural networks. The concept of truncated entropy is introduced to characterize the training property. Specifically, through comprehensive experimental and theoretical analyses conducted on random feature models and two-layer neural networks, we discover that the defined truncated entropy serves as a reliable metric for quantifying the residual loss of random feature models and the training speed of neural networks for both AD and FD methods. Our experimental and theoretical analyses demonstrate that, from a training perspective, AD outperforms FD in solving partial differential equations.

[34]  arXiv:2405.14270 (cross-list from cs.LG) [pdf, other]

Title: Sparse $L^1$-Autoencoders for Scientific Data Compression

Authors: Matthias Chung, Rick Archibald, Paul Atzberger, Jack Michael Solomon

Comments: 11 pages, 6 figures

Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Numerical Analysis (math.NA)

Scientific datasets present unique challenges for machine learning-driven compression methods, including more stringent requirements on accuracy and mitigation of potential invalidating artifacts. Drawing on results from compressed sensing and rate-distortion theory, we introduce effective data compression methods by developing autoencoders using high dimensional latent spaces that are $L^1$-regularized to obtain sparse low dimensional representations. We show how these information-rich latent spaces can be used to mitigate blurring and other artifacts to obtain highly effective data compression methods for scientific data. We demonstrate our methods for short angle scattering (SAS) datasets showing they can achieve compression ratios around two orders of magnitude and in some cases better. Our compression methods show promise for use in addressing current bottlenecks in transmission, storage, and analysis in high-performance distributed computing environments. This is central to processing the large volume of SAS data being generated at shared experimental facilities around the world to support scientific investigations. Our approaches provide general ways for obtaining specialized compression methods for targeted scientific datasets.

[35]  arXiv:2405.14321 (cross-list from cs.MS) [pdf, other]

Title: An 808 Line Phasor-Based Ddehomogenisation Matlab Code For Multi-Scale Topology Optimisation

Authors: Rebekka Varum Woldseth, Ole Sigmund, Peter Dørffler Ladegaard Jensen

Subjects: Mathematical Software (cs.MS); Numerical Analysis (math.NA); Optimization and Control (math.OC)

This work presents an 808-line Matlab educational code for combined multi-scale topology optimisation and phasor-based dehomogenisation titled deHomTop808. The multi-scale formulation utilises homogenisation of optimal microstructures to facilitate efficient coarse-scale optimisation. Dehomogenisation allows for a high-resolution single-scale reconstruction of the optimised multi-scale structure, achieving minor losses in structural performance, at a fraction of the computational cost, compared to its large-scale topology optimisation counterpart. The presented code utilises stiffness optimal Rank-2 microstructures to minimise the compliance of a single-load case problem, subject to a volume fraction constraint. By exploiting the inherent efficiency benefits of the phasor-based dehomogenisation procedure, on-the-fly dehomogenisation to a single-scale structure is obtained. The presented code includes procedures for structural verification of the final dehomogenised structure by comparison to the multi-scale solution. The code is introduced in terms of the underlying theory and its major components, including examples and potential extensions, and can be downloaded from https://github.com/peterdorffler/deHomTop808.git.

[36]  arXiv:2405.14373 (cross-list from math.PR) [pdf, other]

Title: Skew-symmetric schemes for stochastic differential equations with non-Lipschitz drift: an unadjusted Barker algorithm

Authors: Samuel Livingstone, Nikolas Nüsken, Giorgos Vasdekis, Rui-Yang Zhang

Comments: 43 pages, 3 figures Keywords: Skew-symmetric distributions, Stochastic differential equations, Sampling algorithms, Markov Chain Monte Carlo,

Subjects: Probability (math.PR); Numerical Analysis (math.NA); Computation (stat.CO)

We propose a new simple and explicit numerical scheme for time-homogeneous stochastic differential equations. The scheme is based on sampling increments at each time step from a skew-symmetric probability distribution, with the level of skewness determined by the drift and volatility of the underlying process. We show that as the step-size decreases the scheme converges weakly to the diffusion of interest. We then consider the problem of simulating from the limiting distribution of an ergodic diffusion process using the numerical scheme with a fixed step-size. We establish conditions under which the numerical scheme converges to equilibrium at a geometric rate, and quantify the bias between the equilibrium distributions of the scheme and of the true diffusion process. Notably, our results do not require a global Lipschitz assumption on the drift, in contrast to those required for the Euler--Maruyama scheme for long-time simulation at fixed step-sizes. Our weak convergence result relies on an extension of the theory of Milstein \& Tretyakov to stochastic differential equations with non-Lipschitz drift, which could also be of independent interest. We support our theoretical results with numerical simulations.

[37]  arXiv:2405.14827 (cross-list from math.OC) [pdf, other]

Title: An augmented Lagrangian trust-region method with inexact gradient evaluations to accelerate constrained optimization problems using model hyperreduction

Authors: Tianshu Wen, Matthew J. Zahr

Comments: 37 pages, 8 tables, 6 figures. arXiv admin note: text overlap with arXiv:2206.09942

Subjects: Optimization and Control (math.OC); Numerical Analysis (math.NA)

We present an augmented Lagrangian trust-region method to efficiently solve constrained optimization problems governed by large-scale nonlinear systems with application to partial differential equation-constrained optimization. At each major augmented Lagrangian iteration, the expensive optimization subproblem involving the full nonlinear system is replaced by an empirical quadrature-based hyperreduced model constructed on-the-fly. To ensure convergence of these inexact augmented Lagrangian subproblems, we develop a bound-constrained trust-region method that allows for inexact gradient evaluations, and specialize it to our specific setting that leverages hyperreduced models. This approach circumvents a traditional training phase because the models are built on-the-fly in accordance with the requirements of the trust-region convergence theory. Two numerical experiments (constrained aerodynamic shape design) demonstrate the convergence and efficiency of the proposed work. A speedup of 12.7x (for all computational costs, even costs traditionally considered "offline" such as snapshot collection and data compression) relative to a standard optimization approach that does not leverage model reduction is shown.

Replacements for Fri, 24 May 24

[38]  arXiv:2209.03844 (replaced) [pdf, other]

Title: Fast, high-order numerical evaluation of volume potentials via polynomial density interpolation

Authors: Thomas G. Anderson, Marc Bonnet, Luiz M. Faria, Carlos Pérez-Arancibia

Subjects: Numerical Analysis (math.NA); Computational Physics (physics.comp-ph)

[39]  arXiv:2212.07392 (replaced) [pdf, other]

Title: A two level approach for simulating Bose-Einstein condensates by localized orthogonal decomposition

Authors: Christian Döding, Patrick Henning, Johan Wärnegård

Subjects: Numerical Analysis (math.NA)

[40]  arXiv:2302.10684 (replaced) [pdf, other]

Title: Contraction and Convergence Rates for Discretized Kinetic Langevin Dynamics

Authors: Benedict Leimkuhler, Daniel Paulin, Peter A. Whalley

Comments: 34 pages, 1 figure

Journal-ref: SIAM Journal on Numerical Analysis, 62(3):1226-1258, 2024

Subjects: Numerical Analysis (math.NA); Computation (stat.CO)

[41]  arXiv:2308.01705 (replaced) [pdf, ps, other]

Title: Randomized approximation of summable sequences -- adaptive and non-adaptive

Authors: Robert Kunsch, Erich Novak, Marcin Wnuk

Subjects: Numerical Analysis (math.NA); Functional Analysis (math.FA); Probability (math.PR)

[42]  arXiv:2310.10272 (replaced) [pdf, other]

Title: A penalized Allen-Cahn equation for the mean curvature flow of thin structures

Authors: Elie Bretin, Chih-Kang Huang, Simon Masnou

Comments: 28 pages, 11 figures

Subjects: Numerical Analysis (math.NA)

[43]  arXiv:2310.20056 (replaced) [pdf, other]

Title: On the data-driven description of lattice materials mechanics

Authors: Ismael Ben-Yelun, Luis Irastorza-Valera, Luis Saucedo-Mora, Francisco Javier Montáns, Francisco Chinesta

Subjects: Numerical Analysis (math.NA)

[44]  arXiv:2401.08361 (replaced) [pdf, other]

Title: Adjoint Monte Carlo Method

Authors: Russel Caflisch, Yunan Yang

Comments: 39 pages, 7 figures

Subjects: Numerical Analysis (math.NA); Computational Physics (physics.comp-ph)

[45]  arXiv:2401.16896 (replaced) [pdf, other]

Title: Parallelly Sliced Optimal Transport on Spheres and on the Rotation Group

Authors: Michael Quellmalz, Léo Buecher, Gabriele Steidl

Comments: 40 pages, 11 figures

Subjects: Numerical Analysis (math.NA); Optimization and Control (math.OC)

[46]  arXiv:2404.19133 (replaced) [pdf, other]

Title: Parameterized Wasserstein Gradient Flow

Authors: Yijie Jin, Shu Liu, Hao Wu, Xiaojing Ye, Haomin Zhou

Subjects: Numerical Analysis (math.NA)

[47]  arXiv:2405.09414 (replaced) [pdf, other]

Title: Improving the convergence analysis of linear subdivision schemes

Authors: Nira Dyn, Nir Sharon

Subjects: Numerical Analysis (math.NA)

[48]  arXiv:2405.10923 (replaced) [pdf, other]

Title: Randomized Householder QR

Authors: Laura Grigori, Edouard Timsit

Subjects: Numerical Analysis (math.NA)

[49]  arXiv:1901.05535 (replaced) [pdf, other]

Title: Weak convergence rates for temporal numerical approximations of stochastic wave equations with multiplicative noise

Authors: Sonja Cox, Arnulf Jentzen, Felix Lindner

Comments: 41 pages, 1 figure; numerical simulations added, typos corrected, references added

Subjects: Probability (math.PR); Numerical Analysis (math.NA)

[50]  arXiv:2305.12205 (replaced) [pdf, other]

Title: Vocabulary for Universal Approximation: A Linguistic Perspective of Mapping Compositions

Authors: Yongqiang Cai

Comments: ICML2024

Subjects: Machine Learning (cs.LG); Dynamical Systems (math.DS); Numerical Analysis (math.NA)

[51]  arXiv:2310.04396 (replaced) [pdf, other]

Title: Interpolating Parametrized Quantum Circuits using Blackbox Queries

Authors: Lars Simon, Holger Eble, Hagen-Henrik Kowalski, Manuel Radons

Comments: 27 pages, 3 figures, 1 table

Subjects: Quantum Physics (quant-ph); Numerical Analysis (math.NA)

[52]  arXiv:2311.05025 (replaced) [pdf, other]

Title: Unbiased Kinetic Langevin Monte Carlo with Inexact Gradients

Authors: Neil K. Chada, Benedict Leimkuhler, Daniel Paulin, Peter A. Whalley

Comments: 99 Pages, 13 Figures

Subjects: Computation (stat.CO); Numerical Analysis (math.NA); Methodology (stat.ME); Machine Learning (stat.ML)

[53]  arXiv:2401.00275 (replaced) [pdf, other]

Title: An $\ell^1$-Plug-and-Play Approach for MPI Using a Zero Shot Denoiser with Evaluation on the 3D Open MPI Dataset

Authors: Vladyslav Gapyak, Corinna Rentschler, Thomas März, Andreas Weinmann

Comments: 74 pages, 6 figures, additional supplementary material

Subjects: Image and Video Processing (eess.IV); Computer Vision and Pattern Recognition (cs.CV); Machine Learning (cs.LG); Numerical Analysis (math.NA)

[54]  arXiv:2401.12649 (replaced) [pdf, other]

Title: Space-time unfitted finite elements on moving explicit geometry representations

Authors: Santiago Badia, Pere A. Martorell, Francesc Verdugo

Subjects: Computational Engineering, Finance, and Science (cs.CE); Numerical Analysis (math.NA)

[55]  arXiv:2401.17472 (replaced) [pdf, other]

Title: Convergence of the deep BSDE method for stochastic control problems formulated through the stochastic maximum principle

Authors: Zhipeng Huang, Balint Negyesi, Cornelis W. Oosterlee

Subjects: Optimization and Control (math.OC); Numerical Analysis (math.NA); Computational Finance (q-fin.CP)

[56]  arXiv:2404.14688 (replaced) [pdf, other]

Title: FMint: Bridging Human Designed and Data Pretrained Models for Differential Equation Foundation Model

Authors: Zezheng Song, Jiaxin Yuan, Haizhao Yang

Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computational Engineering, Finance, and Science (cs.CE); Dynamical Systems (math.DS); Numerical Analysis (math.NA)

[57]  arXiv:2404.19267 (replaced) [pdf, ps, other]

Title: Temporal Evolution of Bradford Curves in Specialized Library Contexts

Authors: Haobai Xue, Xian Liu

Subjects: Digital Libraries (cs.DL); Numerical Analysis (math.NA)

[58]  arXiv:2405.12823 (replaced) [pdf, other]

Title: Chordal-NMF with Riemannian Multiplicative Update

Authors: Flavia Esposito, Andersen Ang

Comments: 32 pages, 7 figures, 3 tables. arXiv admin note: text overlap with arXiv:1907.02404 by other authors

Subjects: Optimization and Control (math.OC); Numerical Analysis (math.NA)

• New submissions
• Cross-lists
• Replacements