Search

Simplicial complexes are generalizations of classical graphs. Their homology groups are widely used to characterize the structure and the topology of data in e.g. chemistry, neuroscience, and transportation networks. In this work we assume we are given a simplicial complex and that we can act on its underlying graph, formed by the set of 1-simplices, and we investigate the stability of its homology with respect to perturbations of the edges in such graph. Precisely, exploiting the isomorphism between the homology groups and the higher-order Laplacian operators, we propose a numerical method to compute the smallest graph perturbation sufficient to change the dimension of the simplex's Hodge homology. Our approach is based on a matrix nearness problem formulated as a matrix differential equation, which requires an appropriate weighting and normalizing procedure for the boundary operators acting on the Hodge algebra's homology groups. We develop a bilevel optimization procedure suitable for the formulated matrix nearness problem and illustrate the method's performance on a variety of synthetic quasi-triangulation datasets and real-world transportation networks. [ABSTRACT FROM AUTHOR]

We consider piecewise-smooth dynamical systems, i.e., systems of ordinary differential equations switching between different sets of equations on distinct domains, separated by hyper-surfaces. As is well-known, when the solution approaches a discontinuity manifold, a classical solution may cease to exist. For this reason, starting with the pioneering work of Filippov, a concept of weak solution (also known as sliding mode) has been introduced and studied. Nowadays, the solution of piecewise-smooth dynamical systems in and close to discontinuity manifolds is well understood, if the manifold consists locally of a single discontinuity hyper-surface or of the intersection of two discontinuity hyper-surfaces. The present work presents partial results on the solution in and close to discontinuity manifolds of codimension 3 and higher. [ABSTRACT FROM AUTHOR]

This article considers the numerical treatment of piecewise-smooth dynamical systems. Classical solutions as well as sliding modes up to codimension-2 are treated. An algorithm is presented that, in the case of non-uniqueness, selects a solution that is the formal limit solution of a regularized problem. The numerical solution of a regularized differential equation, which creates stiffness and often also high oscillations, is avoided. [ABSTRACT FROM AUTHOR]

In this article, a new method is proposed to approximate the rightmost eigenpair of certain matrix-valued linear operators, in a low-rank setting. First, we introduce a suitable ordinary differential equation, whose solution allows us to approximate the rightmost eigenpair of the linear operator. After analyzing the behaviour of its solution on the whole space, we project the ODE on a low-rank manifold of prescribed rank and correspondingly analyze the behaviour of its solutions. For a general linear operator we prove that—under generic assumptions—the solution of the ODE converges globally to its leading eigenmatrix. The analysis of the projected operator is more subtle due to its nonlinearity; when ca is self-adjoint, we are able to prove that the associated low-rank ODE converges (at least locally) to its rightmost eigenmatrix in the low-rank manifold, a property which appears to hold also in the more general case. Two explicit numerical methods are proposed, the second being an adaptation of the projector splitting integrator proposed recently by Lubich and Oseledets. The numerical experiments show that the method is effective and competitive. [ABSTRACT FROM AUTHOR]

We generalize ideas in the recent literature and develop new ones in order to propose a general class of contour integral methods for linear convection–diffusion PDEs and in particular for those arising in finance. These methods aim to provide a numerical approximation of the solution by computing its inverse Laplace transform. The choice of the integration contour is determined by the computation of a few suitably weighted pseudo-spectral level sets of the leading operator of the equation. Parabolic and hyperbolic profiles proposed in the literature are investigated and compared to the elliptic contour originally proposed by Guglielmi, López-Fernández and Nino 2020, see Guglielmi et al. (Math Comput 89:1161–1191, 2020). In summary, the article provides a comparison among three different integration profiles; proposes a new fast pseudospectral roaming method; optimizes the selection of time windows on which one may arbitrarily approximate the solution by no extra computational cost with respect to the case of a fixed time instant; focuses extensively on computational aspects and it is the reference of the MATLAB code [20], where all algorithms described here are implemented. [ABSTRACT FROM AUTHOR]

In this article, we propose a new method for low-rank completion of a large sparse matrix, subject to non-negativity constraint. As a challenging prototype of this problem, we have in mind the well-known Netflix problem. Our method is based on the derivation of a constrained gradient system and its numerical integration. The methods we propose are based on the constrained minimization of a functional associated to the low-rank completion matrix having minimal distance to the given matrix. In the main 2-level method, the low-rank matrix is expressed in the form of the non-negative factorization X = εUVT, where the factors U and V are assumed to be normalized with unit Frobenius norm. In the inner level—for a given ε—we minimize the functional; in the outer level, we tune the parameter ε until we reach a solution. Numerical experiments on well-known large test matrices show the effectiveness of the method when compared with other algorithms available in the literature. [ABSTRACT FROM AUTHOR]

In this article, we consider the problems (unsolved in the literature) of computing the nearest normal matrix X to a given non-normal matrix A, under certain constraints, that are (i) if A is real, we impose that also X is real; (ii) if A has known entries on a given sparsity pattern Ω and unknown/uncertain entries otherwise, we impose to X the constraint xij = aij for all entries (i,j) in the pattern Ω. As far as we know, there do not exist in the literature specific algorithms aiming to solve these problems. For the case in which all entries of A can be modified, there exists an algorithm by Ruhe, which is able to compute the closest normal matrix. However, if A is real, the closest computed matrix by Ruhe's algorithm might be complex, which motivates the development of a different algorithm preserving reality. Normality is characterized in a very large number of ways; in this article, we consider the property that the square of the Frobenius norm of a normal matrix is equal to the sum of the squares of the moduli of its eigenvalues. This characterization allows us to formulate as equivalent problem the minimization of a functional of an unknown matrix, which should be normal, fulfill the required constraints, and have minimal distance from the given matrix A. [ABSTRACT FROM AUTHOR]

Computing the greatest common divisor of a set of polynomials is a problem which plays an important role in different fields, such as linear system, control, and network theory. In practice, the polynomials are obtained through measurements and computations, so that their coefficients are inexact. This poses the problem of computing an approximate common factor. We propose an improvement and a generalization of the method recently proposed in Guglielmi et al. (SIAM J. Numer. Anal. 55, 1456–1482, 2017), which restates the problem as a (structured) distance to singularity of the Sylvester matrix. We generalize the algorithm in order to work with more than 2 polynomials and to compute an Approximate GCD (Greatest Common Divisor) of degree k ≥ 1; moreover, we show that the algorithm becomes faster by replacing the eigenvalues by the singular values. [ABSTRACT FROM AUTHOR]

Piece-wise smooth differential equations (their regularization, numerical integration, and classification of solutions) is the topic of the present work. The behaviour close to one discontinuity surface and also the entering into the intersection of two discontinuity surfaces is well understood. Here, we study the solutions that exit a codimension-2 sliding mode. Some results are expected, others come as a surprise. We are able to explain situations, where difficulties in numerical computations are reported in the recent literature. The analysis is based on asymptotic expansions for singularly perturbed problems and on the study of a time-parameterized two-dimensional dynamical system (hidden dynamics). Various situations are illustrated by examples. [ABSTRACT FROM AUTHOR]

We present a new approach for constructing polytope Lyapunov functions for continuous-time linear switching systems (LSS). This allows us to decide the stability of LSS and to compute the Lyapunov exponent with a good precision in relatively high dimensions. The same technique is also extended for stabilizability of positive systems by evaluating a polytope concave Lyapunov function ('antinorm') in the cone. The method is based on a suitable discretization of the underlying continuous system and provides both a lower and an upper bound for the Lyapunov exponent. The absolute error in the Lyapunov exponent computation is estimated from above and proved to be linear in the dwell time. The practical efficiency of the new method is demonstrated in several examples and in the list of numerical experiments with randomly generated matrices of dimensions up to 10 (for general linear systems) and up to 100 (for positive systems). The development of the method is based on several theoretical results proved in the paper: the existence of monotone invariant norms and antinorms for positively irreducible systems, the equivalence of all contractive norms for stable systems and the linear convergence theorem. [ABSTRACT FROM AUTHOR]

For a Hamiltonian matrix with purely imaginary eigenvalues, we aim to determine the nearest Hamiltonian matrix such that some or all eigenvalues leave the imaginary axis. Conversely, for a Hamiltonian matrix with all eigenvalues lying off the imaginary axis, we look for a nearest Hamiltonian matrix that has a pair of imaginary eigenvalues. The Hamiltonian matrices can be allowed to be complex or restricted to be real. Such Hamiltonian matrix nearness problems are motivated by applications such as the analysis of passive control systems. They are closely related to the problem of determining extremal points of Hamiltonian pseudospectra. We obtain a characterization of optimal perturbations, which turn out to be of low rank and are attractive stationary points of low-rank differential equations that we derive. We use a two-level approach, where in the inner level we determine extremal points of the Hamiltonian $$\varepsilon $$ -pseudospectrum for a given $$\varepsilon $$ by following the low-rank differential equations into a stationary point, and on the outer level we optimize for $$\varepsilon $$ . This permits us to give fast algorithms-exhibiting quadratic convergence-for solving the considered Hamiltonian matrix nearness problems. [ABSTRACT FROM AUTHOR]

For neutral delay differential equations the right-hand side can be multi-valued, when one or several delayed arguments cross a breaking point. This article studies a regularization via a singularly perturbed problem, which smooths the vector field and removes the discontinuities in the derivative of the solution. A low-dimensional dynamical system is presented, which characterizes the kind of generalized solution that is approximated. For the case that the solution of the regularized problem has high frequency oscillations around a codimension-2 weak solution of the original problem, a new stabilizing regularization is proposed and analyzed. [ABSTRACT FROM AUTHOR]

In this paper, we are concerned with numerical solution of piecewise smooth initial value problems. Of specific interest is the case when the discontinuities occur on a smooth manifold of co-dimension 2, intersection of two co-dimension 1 singularity surfaces, and which is nodally attractive for nearby dynamics. In this case of a co-dimension 2 attracting sliding surface, we will give some results relative to two prototypical time and space regularizations. We will show that, unlike the case of co-dimension 1 discontinuity surface, in the case of co-dimension 2 discontinuity surface the behavior of the regularized problems is strikingly different. On the one hand, the time regularization approach will not select a unique sliding mode on the discontinuity surface, thus maintaining the general ambiguity of how to select a Filippov vector field in this case. On the other hand, the proposed space regularization approach is not ambiguous, and there will always be a unique solution associated to the regularized vector field, which will remain close to the original co-dimension 2 surface. We will further clarify the limiting behavior (as the regularization parameter goes to 0) of the proposed space regularization to the solution associated to the sliding vector field of Dieci and Lopez (Numer Math 117:779-811, ). Numerical examples will be given to illustrate the different cases and to provide some preliminary exploration in the case of co-dimension 3 discontinuity surface. [ABSTRACT FROM AUTHOR]

We address the problem of the exact computation of two joint spectral characteristics of a family of linear operators, the joint spectral radius (JSR) and the lower spectral radius (LSR), which are well-known different generalizations to a set of operators of the usual spectral radius of a linear operator. In this paper we develop a method which-under suitable assumptions-allows us to compute the JSR and the LSR of a finite family of matrices exactly. We remark that so far no algorithm has been available in the literature to compute the LSR exactly. The paper presents necessary theoretical results on extremal norms (and on extremal antinorms) of linear operators, which constitute the basic tools of our procedures, and a detailed description of the corresponding algorithms for the computation of the JSR and LSR (the last one restricted to families sharing an invariant cone). The algorithms are easily implemented, and their descriptions are short. If the algorithms terminate in finite time, then they construct an extremal norm (in the JSR case) or antinorm (in the LSR case) and find their exact values; otherwise, they provide upper and lower bounds that both converge to the exact values. A theoretical criterion for termination in finite time is also derived. According to numerical experiments, the algorithm for the JSR finds the exact value for the vast majority of matrix families in dimensions ≤20. For nonnegative matrices it works faster and finds the JSR in dimensions of order 100 within a few iterations; the same is observed for the algorithm computing the LSR. To illustrate the efficiency of the new method, we apply it to give answers to several conjectures which have been recently stated in combinatorics, number theory, and formal language theory. [ABSTRACT FROM AUTHOR]

In this paper we consider some classes of difference equations, including the well-known Clark model, and study the stability of their solutions. In order to do that we introduce a property, namely semicontractivity, and study relations between ‘semi-contractive’ functions and sufficient conditions for the solution of the difference equation to be globally asymptotically stable. Moreover, we establish new sufficient conditions for the solution to be globally asymptotically stable, and we improve the ‘3/2 criteria’ type stability conditions. [ABSTRACT FROM AUTHOR]

We consider Runge–Kutta methods applied to delay differential equations $y'(t)=ay(t)+by(t-1)$ with real a and b. If the numerical solution tends to zero whenever the exact solution does, the method is called $\tau (0)$ -stable. Using the theory of order stars we characterize high-order symmetric methods with this property. In particular, we prove that all Gauss methods are $\tau (0)$ -stable. Furthermore, we present sufficient conditions and we give evidence that also the Radau methods are $\tau (0)$ -stable. We conclude this article with some comments on the case where a and b are complex numbers. [ABSTRACT FROM AUTHOR]

In this paper asymptotic stability properties of Runge-Kutta (R-K) methods for delay differential equations (DDEs) are considered with respect to the following test equation: $ \begin{eqnarray*} \left\{ \begin{array}{ccl} y'(t) & = & a\, y(t) + b\, y(t\,-\tau), \\[0.3cm] y(t) & = & g(t), \end{array} \right. \hskip 0.3cm \begin{array}{r} t > 0, \\[0.3cm] -\tau \leq t \leq 0, \end{array} \end{eqnarray*} $ where $a,b \in {\Bbb R} ,\,\tau > 0$ and $g(t)$ is a continuous real-valued function. In the last few years, stability properties of R-K methods applied to DDEs have been studied by numerous authors who have considered regions of asymptotic stability for “any positive delay” (and thus independent of the specific value of $\tau$ ). In this work we direct attention at the dependence of stability regions on a fixed delay $\tau$ . In particular, natural Runge-Kutta methods for DDEs are extensively examined. [ABSTRACT FROM AUTHOR]