One can estimate the change of the Perron and Fiedler values for a connected network when the weight of an edge is perturbed by analyzing relevant entries of the Perron and Fiedler vectors. This is helpful for identifying edges whose weight perturbation causes the largest change in the Perron and Fiedler values. It also is important to investigate the sensitivity of the Perron and Fiedler vectors to perturbations. Applications of the perturbation analysis include the identification of edges that are critical for the structural robustness of the network.
We construct a semi-Lagrangian scheme for first-order, time-dependent, and non-local Mean Field Games. The convergence of the scheme to a weak solution of the system is analyzed by exploiting a key monotonicity property. To solve the resulting discrete problem, we implement a Learning Value Algorithm, prove its convergence, and propose an acceleration strategy based on a Policy iteration method. Finally, we present numerical experiments that validate the effectiveness of the proposed schemes and show that the accelerated version significantly improves performance.
We introduce a fully discrete scheme to solve a class of high-dimensional Mean Field Games systems. Our approach couples semi-Lagrangian (SL) time discretizations with Tensor-Train (TT) decompositions to tame the curse of dimensionality. By reformulating the classical Hamilton-Jacobi-Bellman and Fokker-Planck equations as a sequence of advection-diffusion-reaction subproblems within a smoothed policy iteration, we construct both first and second order in time SL schemes. The TT format and appropriate quadrature rules reduce storage and computational cost from exponential to polynomial in the dimension. Numerical experiments demonstrate that our TT-accelerated SL methods achieve their theoretical convergence rates, exhibit modest growth in memory usage and runtime with dimension, and significantly outperform grid-based SL in accuracy per CPU second.
Elisabetta Carlini, Athena Picarelli, Francisco J. Silva
We study the numerical approximation of time-dependent, possibly degenerate, second-order Hamilton-Jacobi-Bellman equations in bounded domains with nonhomogeneous Dirichlet boundary conditions. It is well known that convergence towards the exact solution of the equation, considered here in the viscosity sense, holds if the scheme is monotone, consistent, and stable. While standard finite difference schemes are, in general, not monotone, the so-called semi-Lagrangian schemes are monotone by construction. On the other hand, these schemes make use of a wide stencil and, when the equation is set in a bounded domain, this typically causes an overstepping of the boundary and hence the loss of consistency. We propose here a semi-Lagrangian scheme defined on an unstructured mesh, with a suitable treatment at grid points near the boundary to preserve consistency, and show its convergence for problems where the viscosity solution can even be discontinuous. We illustrate the numerical convergence in several tests, including degenerate and first-order equations.
In this paper, we analyze the capacity of super-resolution of one-dimensional positive sources. In particular, we consider the same setting as in [arXiv:1904.09186v2 [math.NA]] and generalize the results there to the case of super-resolving positive sources. To be more specific, we consider resolving $d$ positive point sources with $p \leqslant d$ nodes closely spaced and forming a cluster, while the rest of the nodes are well separated. Similarly to [arXiv:1904.09186v2 [math.NA]], our results show that when the noise level $ε\lesssim \mathrm{SRF}^{-2 p+1}$, where $\mathrm{SRF}=(ΩΔ)^{-1}$ with $Ω$ being the cutoff frequency and $Δ$ the minimal separation between the nodes, the minimax error rate for reconstructing the cluster nodes is of order $\frac{1}Ω \mathrm{SRF}^{2 p-2} ε$, while for recovering the corresponding amplitudes $\left\{a_j\right\}$ the rate is of order $\mathrm{SRF}^{2 p-1} ε$. For the non-cluster nodes, the corresponding minimax rates for the recovery of nodes and amplitudes are of order $\fracεΩ$ and $ε$, respectively. Our numerical experiments show that the Matrix Pencil method achieves the above optimal bounds when resolving the positive sources.
This paper is concerned with the distance of a symmetric tridiagonal Toeplitz matrix $T$ to the variety of similarly structured singular matrices, and with determining the closest matrix to $T$ in this variety. Explicit formulas are presented, that exploit the analysis of the sensitivity of the spectrum of $T$ with respect to structure-preserving perturbations of its entries.
Complex systems that consist of different kinds of entities that interact in different ways can be modeled by multilayer networks. This paper uses the tensor formalism with the Einstein tensor product to model this type of networks. Several centrality measures, that are well known for single-layer networks, are extended to multilayer networks using tensors and their properties are investigated. In particular, subgraph centrality based on the exponential and resolvent of a tensor are considered. Krylov subspace methods are introduced for computing approximations of different measures for large multilayer networks.
We consider an LQR optimal control problem with partially unknown dynamics. We propose a new model-based online algorithm to obtain an approximation of the dynamics $and$ the control at the same time during a single simulation.
Elisa Calzola, Elisabetta Carlini, Xavier Dupuis
et al.
We investigate in this work a fully-discrete semi-Lagrangian approximation of second order possibly degenerate Hamilton-Jacobi-Bellman (HJB) equations on a bounded domain with oblique boundary conditions. These equations appear naturally in the study of optimal control of diffusion processes with oblique reflection at the boundary of the domain. The proposed scheme is shown to satisfy a consistency type property, it is monotone and stable. Our main result is the convergence of the numerical solution towards the unique viscosity solution of the HJB equation. The convergence result holds under the same asymptotic relation between the time and space discretization steps as in the classical setting for semi-Lagrangian schemes. We present some numerical results that confirm the numerical convergence of the scheme.
Many interesting applications of hyperbolic systems of equations are stiff, and require the time step to satisfy restrictive stability conditions. One way to avoid small time steps is to use implicit time integration. Implicit integration is quite straightforward for first order schemes. High order schemes instead need also to control spurious oscillations, which requires limiting in space and time also in the implicit case. We propose a framework to simplify considerably the application of high order non oscillatory schemes through the introduction of a low order implicit predictor, which is used both to set up the nonlinear weights of a standard high order space reconstruction, and to achieve limiting in time. In this preliminary work, we concentrate on the case of a third order scheme, based on DIRK integration in time and CWENO reconstruction in space. The numerical tests involve linear and nonlinear scalar conservation laws.
Given a structured matrix $A$ we study the problem of finding the closest normal matrix with the same structure. The structures of our interest are: Hamiltonian, skew-Hamiltonian, per-Hermitian, and perskew-Hermitian. We develop a structure-preserving Jacobi-type algorithm for finding the closest normal structured matrix and show that such algorithm converges to a stationary point of the objective function.
Luca Bonaventura, Elisabetta Carlini, Elisa Calzola
et al.
We propose a second order, fully semi-Lagrangian method for the numerical solution of systems of advection-diffusion-reaction equations, which employs a semi-Lagrangian approach to approximate in time both the advective and the diffusive terms. Standard interpolation procedures are used for the space discretization on structured and unstructured meshes. The proposed method allows for large time steps, while avoiding the solution of large linear systems, which would be required by an implicit time discretization technique. Numerical experiments demonstrate the effectiveness of the proposed approach and its superior efficiency with respect to more conventional explicit and implicit time discretizations
We suggest guaranteed, robust a posteriori error bounds for approximate solutions of the reaction-diffusion equations, modeled by the equation $-\Delta u+\sigma u= f$ in $\Omega$ with any $\sigma={\mathrm{const}}\ge 0$. We also term our bounds consistent due to one specific property. It assumes that their orders of accuracy in respect to mesh size $h$ are the same with the respective not improvable in the order a priori bounds. Additionally, it assumes that the pointed out equality of the orders is provided by the testing flaxes not subjected to equilibration. For any $\sigma\in [0,\sigma_*]$, the rirght part of the new general bound of the paper contains, besides the usual diffusion term, the $L_2$ norm of the residual with the factor $1/\sqrt{\sigma_*}$, where $\sigma_*$ is some critical value. For solutions by the finite element method, it is estimated as $\sigma_*\ge ch^{-2},\,\,c={\mathrm{const}}$, if $\partial \Omega$ is sufficiently smooth and the finite element space is of the 1$^{\mathrm{st}}$ order of accuracy at least. In general, at the derivation of a posteriori bounds, consistency is achieved by taking adequately into account the difference of the orders of the $L_2$ and $H^1$ error norms, that can be done in various ways with accordingly introduced $\sigma_*$. Two advantages of the obtained consistent a posteriori error bounds deserve attention. They are better accuracy and the possibility to avoid the use of the equilibration in the flax recovery procedures, that may greatly simplify these procedures and make them much more universal. The technique of obtaining the consistent a posteriori bounds was briefly exposed by the author in [arXiv:1702.00433v1 [math.NA], 1 Feb 2017] and [$Doklady Mathematics$, ${\mathbf{96}}$ (1), 2017, 380-383].