Spectral condition‐number estimation of large sparse matrices

We describe a randomized Krylov‐subspace method for estimating the spectral condition number of a real matrix A or indicating that it is numerically rank deficient. The main difficulty in estimating the condition number is the estimation of the smallest singular value ${\sigma }_{\min }$ of A. Our method estimates this value by solving a consistent linear least squares problem with a known solution using a specific Krylov‐subspace method called LSQR. In this method, the forward error tends to concentrate in the direction of a right singular vector corresponding to ${\sigma }_{\min }$. Extensive experiments show that the method is able to estimate well the condition number of a wide array of matrices. It can sometimes estimate the condition number when running dense singular value decomposition would be impractical due to the computational cost or the memory requirements. The method uses very little memory (it inherits this property from LSQR), and it works equally well on square and rectangular matrices.     

Semi‐active ℋ∞ damping optimization by adaptive interpolation

In this work we consider the problem of semi‐active damping optimization of mechanical systems with fixed damper positions. Our goal is to compute a damping that is locally optimal with respect to the ${?}_{\infty }$‐norm of the transfer function from the exogenous inputs to the performance outputs. We make use of a new greedy method for computing the ${?}_{\infty }$‐norm of a transfer function based on rational interpolation. In this paper, this approach is adapted to parameter‐dependent transfer functions. The interpolation leads to parametric reduced‐order models that can be optimized more efficiently. At the optimizers we then take new interpolation points to refine the reduced‐order model and to obtain updated optimizers. In our numerical examples we show that this approach normally converges fast and thus can highly accelerate the optimization procedure. Another contribution of this work is heuristics for choosing initial interpolation points.     

Data-driven linear complexity low-rank approximation of general kernel matrices: A geometric approach

A general, rectangular kernel matrix may be defined as $K_{ij}=\kappa (x_i,y_j)$ where $\kappa (x,y)$ is a kernel function and where $X={\{x_i\}}_{i=1}^m$ and $Y={\{y_i\}}_{i=1}^n$ are two sets of points. In this paper, we seek a low-rank approximation to a kernel matrix where the sets of points $X$ and $Y$ are large and are arbitrarily distributed, such as away from each other, “intermingled”, identical, and so forth. Such rectangular kernel matrices may arise, for example, in Gaussian process regression where $X$ corresponds to the training data and $Y$ corresponds to the test data. In this case, the points are often high-dimensional. Since the point sets are large, we must exploit the fact that the matrix arises from a kernel function, and avoid forming the matrix, and thus ruling out most algebraic techniques. In particular, we seek methods that can scale linearly or nearly linearly with respect to the size of data for a fixed approximation rank. The main idea in this paper is to geometrically select appropriate subsets of points to construct a low rank approximation. An analysis in this paper guides how this selection should be performed.     

A reduced basis approach to large‐scale pseudospectra computation

For studying spectral properties of a nonnormal matrix $A\in {\mathbb{C}}^{n\times n}$, information about its spectrum σ(A) alone is usually not enough. Effects of perturbations on σ(A) can be studied by computing ε‐pseudospectra, i.e. the level sets of the resolvent norm function $\mathsf{g}(z)=\Vert {(zI?A)}^{?1}{\Vert }_2$. The computation of ε‐pseudospectra requires determining the smallest singular values ${\sigma }_{\min }(zI?A)$ for all z on a portion of the complex plane. In this work, we propose a reduced basis approach to pseudospectra computation, which provides highly accurate estimates of pseudospectra in the region of interest, in particular, for pseudospectra estimates in isolated parts of the spectrum containing few eigenvalues of A. It incorporates the sampled singular vectors of zI ? A for different values of z, and implicitly exploits their smoothness properties. It provides rigorous upper and lower bounds for the pseudospectra in the region of interest. In addition, we propose a domain splitting technique for tackling numerically more challenging examples. We present a comparison of our algorithms to several existing approaches on a number of numerical examples, showing that our approach provides significant improvement in terms of computational time.     

Spectral analysis of Pk Finite Element matrices in the case of Friedrichs–Keller triangulations via Generalized Locally Toeplitz technology

In the present article, we consider a class of elliptic partial differential equations with Dirichlet boundary conditions and where the operator is div(?a( x )?·), with a continuous and positive over $\stackrel{￣}{\mathrm{\Omega }}$, Ω being an open and bounded subset of ${\mathbb{R}}^d$, d≥1. For the numerical approximation, we consider the classical ${\mathbb{P}}_k$ Finite Elements, in the case of Friedrichs–Keller triangulations, leading, as usual, to sequences of matrices of increasing size. The new results concern the spectral analysis of the resulting matrix‐sequences in the direction of the global distribution in the Weyl sense, with a concise overview on localization, clustering, extremal eigenvalues, and asymptotic conditioning. We study in detail the case of constant coefficients on Ω=(0,1)² and we give a brief account in the more involved case of variable coefficients and more general domains. Tools are drawn from the Toeplitz technology and from the rather new theory of Generalized Locally Toeplitz sequences. Numerical results are shown for a practical evidence of the theoretical findings.     

Solving the general joint block diagonalization problem via linearly independent eigenvectors of a matrix polynomial

In this paper, we consider the exact/approximate general joint block diagonalization (GJBD) problem of a matrix set ${\{A_i\}}_{i=0}^p$ ( p ≥ 1), where a nonsingular matrix W (often referred to as a diagonalizer) needs to be found such that the matrices W ^HA_iW 's are all exactly/approximately block‐diagonal matrices with as many diagonal blocks as possible. We show that the diagonalizer of the exact GJBD problem can be given by W = [x₁,x₂,…,x_n]Π, where Π is a permutation matrix and x_i's are eigenvectors of the matrix polynomial $P(\lambda )={\sum }_{i=0}^p{\lambda }^i{A}_i$, satisfying that [x₁,x₂,…,x_n] is nonsingular and where the geometric multiplicity of each λ_i corresponding with x_i is equal to 1. In addition, the equivalence of all solutions to the exact GJBD problem is established. Moreover, a theoretical proof is given to show why the approximate GJBD problem can be solved similarly to the exact GJBD problem. Based on the theoretical results, a three‐stage method is proposed, and numerical results show the merits of the method.     

Asymptotics for the eigenvalues of Toeplitz matrices with a symbol having a power singularity

The present work is devoted to the construction of an asymptotic expansion for the eigenvalues of a Toeplitz matrix $T_n(a)$ as $n$ goes to infinity, with a continuous and real-valued symbol $a$ having a power singularity of degree $\gamma$ with , at one point. The resulting matrix is dense and its entries decrease slowly to zero when moving away from the main diagonal, we apply the so called simple-loop (SL) method for constructing and justifying a uniform asymptotic expansion for all the eigenvalues. Note however, that the considered symbol does not fully satisfy the conditions imposed in previous works, but only in a small neighborhood of the singularity point. In the present work: (i) We construct and justify the asymptotic formulas of the SL method for the eigenvalues ${\lambda }_j(T_n(a))$ with $j⩾\epsilon n$, where the eigenvalues are arranged in nondecreasing order and $\epsilon$ is a sufficiently small fixed number. (ii) We show, with the help of numerical calculations, that the obtained formulas give good approximations in the case . (iii) We numerically show that the main term of the asymptotics for eigenvalues with , formally obtained from the formulas of the SL method, coincides with the main term of the asymptotics constructed and justified in the classical works of Widom and Parter.     

Tensor rank bounds and explicit QTT representations for the inverses of circulant matrices

In this paper, we are concerned with the inversion of circulant matrices and their quantized tensor-train (QTT) structure. In particular, we show that the inverse of a complex circulant matrix $A$, generated by the first column of the form ${(a_0,\dots ,a_{m-1},0,\dots ,0,a_{-n},\dots ,a_{-1})}^{\top }$ admits a QTT representation with the QTT ranks bounded by $(m+n)$. Under certain assumptions on the entries of $A$, we also derive an explicit QTT representation of $A^{-1}$. The latter can be used, for instance, to overcome stability issues arising when numerically solving differential equations with periodic boundary conditions in the QTT format.     

Constructing the field of values of decomposable and general matrices using the ZNN based path following method

This paper describes and develops a fast and accurate path following algorithm that computes the field of values boundary curve $\partial F(A)$ for every conceivable complex or real square matrix $A$. It relies on the matrix flow decomposition algorithm that finds a proper block-diagonal flow representation for the associated hermitean matrix flow ${ℱ}_A(t)=\cos (t)H+\sin (t)K$ under unitary similarity if that is possible. Here ${ℱ}_A(t)$ is the 1-parameter-varying linear combination of the real and skew part matrices $H=(A+A^{\ast })/2$ and $K=(A-A^{\ast })/(2i)$ of $A$. For indecomposable matrix flows, ${ℱ}_A(t)$ has just one block and the ZNN based field of values algorithm works with ${ℱ}_A(t)$ directly. For decomposing flows ${ℱ}_A(t)$, the algorithm decomposes the given matrix $A$ unitarily into block-diagonal form $U^{\ast }AU=\text{diag}(A_j)$ with $j>1$ diagonal blocks $A_j$ whose individual sizes add up to the size of $A$. It then computes the field of values boundaries separately for each diagonal block $A_j$ using the path following ZNN eigenvalue method. The convex hull of all sub-fields of values boundary points $\partial F(A_j)$ finally determines the field of values boundary curve correctly for decomposing matrices $A$. The algorithm removes standard restrictions for path following FoV methods that generally cannot deal with decomposing matrices $A$ due to possible eigencurve crossings of ${ℱ}_A(t)$. Tests and numerical comparisons are included. Our ZNN based method is coded for sequential and parallel computations and both versions run very accurately and fast when compared with Johnson's Francis QR eigenvalue and Bendixson rectangle based method and compute global eigenanalyses of ${ℱ}_A(t_k)$ for large discrete sets of angles $t_k\in [0,2\pi ]$ more slowly.     

Non‐Hermitian perturbations of Hermitian matrix‐sequences and applications to the spectral analysis of the numerical approximation of partial differential equations

This article concerns the spectral analysis of matrix‐sequences which can be written as a non‐Hermitian perturbation of a given Hermitian matrix‐sequence. The main result reads as follows. Suppose that for every n there is a Hermitian matrix X_n of size n and that {X_n}_n～_λf, that is, the matrix‐sequence {X_n}_n enjoys an asymptotic spectral distribution, in the Weyl sense, described by a Lebesgue measurable function f; if $\Vert Y_n{\Vert }_2=o(\sqrt{n})$ with ‖·‖₂ being the Schatten 2 norm, then {X_n+Y_n}_n～_λf. In a previous article by Leonid Golinskii and the second author, a similar result was proved, but under the technical restrictive assumption that the involved matrix‐sequences {X_n}_n and {Y_n}_n are uniformly bounded in spectral norm. Nevertheless, the result had a remarkable impact in the analysis of both spectral distribution and clustering of matrix‐sequences arising from various applications, including the numerical approximation of partial differential equations (PDEs) and the preconditioning of PDE discretization matrices. The new result considerably extends the spectral analysis tools provided by the former one, and in fact we are now allowed to analyze linear PDEs with (unbounded) variable coefficients, preconditioned matrix‐sequences, and so forth. A few selected applications are considered, extensive numerical experiments are discussed, and a further conjecture is illustrated at the end of the article.     

Exceptions and characterization results for type‐1 λ‐designs

Let $X$ be a finite set with $v$ elements, called points and $\beta$ be a family of subsets of $X$, called blocks. A pair $\left(X,\beta \right)$ is called $\lambda$‐design whenever $\mid \beta \mid =\mid X\mid$ and

• 1. for all $B_i,B_j\in \beta ,i\ne j,\mid B_i\cap B_j\mid =\lambda$;
• 2. for all $B_j\in \beta ,\mid B_j\mid =k_j>\lambda$, and not all $k_j$ are equal.

The only known examples of $\lambda$‐designs are so‐called type‐1 designs, which are obtained from symmetric designs by a certain complementation procedure. Ryser and Woodall had independently conjectured that all $\lambda$‐designs are type‐1. Let $r,r^{*}?(r>r^{*})$ be replication numbers of a $\lambda$‐design $D=\left(X,\beta \right)$ and $g=\text{gcd}\left(r?1,r^{*}?1\right),m=\text{gcd}\left(\left(r?r^{*}\right)∕g,\lambda \right)$, and $m\prime =m$, if $m$ is odd and $m\prime =m∕2$, otherwise. For distinct points $x$ and $y$ of $D$, let $\lambda \left(x,y\right)$ denote the number of blocks of $X$ containing $x$ and $y$. We strengthen a lemma of S.S. Shrikhande and N.M. Singhi and use it to prove that if $\frac{r\left(r?1\right)}{\left(v?1\right)}?\frac{k\left(r?r^{*}\right)}{m\prime \left(v?1\right)}$ are not integers for $k=1,2,\text{…},m\prime ?1$, then $D$ is type‐1. As an application of these results, we show that for fixed positive integer $\theta$ there are finitely many nontype‐1 $\lambda$‐designs with $r=r^{*}+\theta$. If $r?r^{*}=27$ or $r?r^{*}=4p$ and $r^{*}\ne {\left(p?1\right)}^2$, or $v=7p+1$ such that $p?1,13\left(\mathrm{mod}21\right)$ and $p?4,9,19,24\left(\mathrm{mod}35\right)$, where $p$ is a positive prime, then $D$ is type‐1. We further obtain several inequalities involving $\lambda (x,y)$, where equality holds if and only if D is type‐1.     

A locally and cubically convergent algorithm for computing 𝒵‐eigenpairs of symmetric tensors

This paper is concerned with computing $\mathrm{??}$‐eigenpairs of symmetric tensors. We first show that computing $\mathrm{??}$‐eigenpairs of a symmetric tensor is equivalent to finding the nonzero solutions of a nonlinear system of equations, and then propose a modified normalized Newton method (MNNM) for it. Our proposed MNNM method is proved to be locally and cubically convergent under some suitable conditions, which greatly improves the Newton correction method and the orthogonal Newton correction method recently provided by Jaffe, Weiss and Nadler since these two methods only enjoy a quadratic rate of convergence. As an application, the unitary symmetric eigenpairs of a complex‐valued symmetric tensor arising from the computation of quantum entanglement in quantum physics are calculated by the MNNM method. Some numerical results are presented to illustrate the efficiency and effectiveness of our method.     

Lower and upper bounds of condition number for Vandermonde-wise matrices and method of fundamental solutions using pseudo radial-lines

Consider the method of fundamental solutions (MFS) for 2D Laplace's equation in a bounded simply connected domain $S$. In the standard MFS, the source nodes are located on a closed contour outside the domain boundary $\mathrm{\Gamma }(=\partial S)$, which is called pseudo-boundary. For circular, elliptic, and general closed pseudo-boundaries, analysis and computation have been studied extensively. New locations of source nodes are proposed along two pseudo radial-lines outside $\mathrm{\Gamma }$. Numerical results are very encouraging and promising. Since the success of the MFS mainly depends on stability, our efforts are focused on deriving the lower and upper bounds of condition number (Cond). The study finds stability properties of new Vandermonde-wise matrices on nodes $x_i\in [a,b]$ with . The Vandermonde-wise matrix is called in this article if it can be decomposed into the standard Vandermonde matrix. New lower and upper bounds of Cond are first derived for the standard Vandermonde matrix, and then for new algorithms of the MFS using two pseudo radial-lines. Both lower and upper bounds of Cond are intriguing in the stability study for the MFS. Numerical experiments are carried out to verify the stability analysis made. Since the fundamental solutions (as $\{\ln |\overline{{PQ}_i}|\}$) are the basis functions of the MFS, new Vandermonde-wise matrices are found. Since the nodes $x_i\in [a,b]$ with may come from approximations and interpolations by the Laurent polynomials with singular part, the conclusions in this article are important not only to the MFS but also to matrix analysis.     

Blow‐up for wave equation with the scale‐invariant damping and combined nonlinearities

In this article, we study the blow‐up of the damped wave equation in the scale‐invariant case and in the presence of two nonlinearities. More precisely, we consider the following equation: $$u_{tt}?\mathrm{\Delta }u+\frac{\mu }{1+t}{u}_t=|u_t{|}^p+|u{|}^q,\text{in}{?}^N\times [0,\infty ),$$ with small initial data. For $\mu <\frac{N(q?1)}{2}$ and μ ∈ (0, μ_?) , where μ_? > 0 is depending on the nonlinearties' powers and the space dimension (μ_? satisfies $(q?1)\left((N+2{\mu }_{?}?1)p?2\right)=4$), we prove that the wave equation, in this case, behaves like the one without dissipation (μ = 0 ). Our result completes the previous studies in the case where the dissipation is given by $\frac{\mu }{{(1+t)}^{\beta }}{u}_t;\beta >1$, where, contrary to what we obtain in the present work, the effect of the damping is not significant in the dynamics. Interestingly, in our case, the influence of the damping term $\frac{\mu }{1+t}{u}_t$ is important.     

Multicolor low‐rank preconditioner for general sparse linear systems

This article presents a multilevel parallel preconditioning technique for solving general large sparse linear systems of equations. Subdomain coloring is invoked to reorder the coefficient matrix by multicoloring the adjacency graph of the subdomains, resulting in a two‐level block diagonal structure. A full binary tree structure $\mathrm{??}$ is then built to facilitate the construction of the preconditioner. A key property that is exploited is the observation that the difference between the inverse of the original matrix and that of its block diagonal approximation is often well approximated by a low‐rank matrix. This property and the block diagonal structure of the reordered matrix lead to a multicolor low‐rank (MCLR) preconditioner. The construction procedure of the MCLR preconditioner follows a bottom‐up traversal of the tree $\mathrm{??}$. All irregular matrix computations, such as ILU factorizations and related triangular solves, are restricted to leaf nodes where these operations can be performed independently. Computations in nonleaf nodes only involve easy‐to‐optimize dense matrix operations. In order to further reduce the number of iteration of the Preconditioned Krylov subspace procedure, we combine MCLR with a few classical block‐relaxation techniques. Numerical experiments on various test problems are proposed to illustrate the robustness and efficiency of the proposed approach for solving large sparse symmetric and nonsymmetric linear systems.     

Fast solution of three-dimensional elliptic equations with randomly generated jumping coefficients by using tensor-structured preconditioners

In this paper, we propose and analyze the numerical algorithms for fast solution of periodic elliptic problems in random media in ${ℝ}^d$, $d=2,3$. Both the two-dimensional (2D) and three-dimensional (3D) elliptic problems are considered for the jumping equation coefficients built as a checkerboard type configuration of bumps randomly distributed on a large $L\times L$, or $L\times L\times L$ lattice, respectively. The finite element method discretization procedure on a 3D $n\times n\times n$ uniform tensor grid is described in detail, and the Kronecker tensor product approach is proposed for fast generation of the stiffness matrix. We introduce tensor techniques for the construction of the low Kronecker rank spectrally equivalent preconditioner in a periodic setting to be used in the framework of the preconditioned conjugate gradient iteration. The discrete 3D periodic Laplacian pseudo-inverse is first diagonalized in the Fourier basis, and then the diagonal matrix is reshaped into a fully populated third-order tensor of size $n\times n\times n$. The latter is approximated by a low-rank canonical tensor by using the multigrid Tucker-to-canonical tensor transform. As an example, we apply the presented solver in numerical analysis of stochastic homogenization method where the 3D elliptic equation should be solved many hundred times, and where for every random sampling of the equation coefficient one has to construct the new stiffness matrix and the right-hand side. The computational characteristics of the presented solver in terms of a lattice parameter $L$ and the grid-size, $n^d$, in both 2D and 3D cases are illustrated in numerical tests. Our solver can be used in various applications where the elliptic problem should be solved for a number of different coefficients for example, in many-particle dynamics, protein docking problems or stochastic modeling.     

Backward error analysis of specified eigenpairs for sparse matrix polynomials

This article studies the unstructured and structured backward error analysis of specified eigenpairs for matrix polynomials. The structures we discuss include $T$-symmetric, $T$-skew-symmetric, Hermitian, skew Hermitian, $T$-even, $T$-odd, $H$-even, $H$-odd, $T$-palindromic, $T$-anti-palindromic, $H$-palindromic, and $H$-anti-palindromic matrix polynomials. Minimally structured perturbations are constructed with respect to Frobenius norm such that specified eigenpairs become exact eigenpairs of an appropriately perturbed matrix polynomial that also preserves sparsity. Further, we have used our results to solve various quadratic inverse eigenvalue problems that arise from real-life applications.     

I‐convexity and Q‐convexity in Orlicz–Bochner function spaces endowed with the Orlicz norm

Some characterizations of I‐convexity and Q‐convexity of Banach space are obtained. Moreover, the criteria is shown for Orlicz–Bochner function spaces $L_M(\mu ,X)$ endowed with the Orlicz norm being I‐convex as well as being Q‐convex.