Search

This paper addresses multilinear systems of equations which arise in various applications such as data mining and numerical partial differential equations. When the multilinear system under consideration involves a nonsingular M -tensor and a nonnegative right-hand side vector, it may have multiple nonnegative solutions. In this paper, we propose an algorithm which can always preserve the nonnegativity of solutions. Theoretically, we show that the sequence generated by the proposed algorithm is a nonnegative componentwise nonincreasing sequence and converges to a nonnegative solution of the system. Numerical results further support the novelty of the proposed method. [ABSTRACT FROM AUTHOR]

This paper is concerned with the inverse problem of constructing a symmetric nonnegative matrix from realizable spectrum. We reformulate the inverse problem as an underdetermined nonlinear matrix equation over a Riemannian product manifold. To solve it, we develop a Riemannian underdetermined inexact Newton dogleg method for solving a general underdetermined nonlinear equation defined between Riemannian manifolds and Euclidean spaces. The global and quadratic convergence of the proposed method is established under some mild assumptions. Then, we solve the inverse problem by applying the proposed method to its equivalent nonlinear matrix equation and a preconditioner for the perturbed normal Riemannian Newton equation is also constructed. Numerical tests show the efficiency of the proposed method for solving the inverse problem. [ABSTRACT FROM AUTHOR]

Modeling complex systems that consist of different types of objects leads to multilayer networks, where nodes in the different layers represent different kinds of objects. Nodes are connected by edges, which have positive weights. A multilayer network is associated with a supra-adjacency matrix. This paper investigates the sensitivity of the communicability in a multilayer network to perturbations of the network by studying the sensitivity of the Perron root of the supra-adjacency matrix. Our analysis sheds light on which edge weights to make larger to increase the communicability of the network, and which edge weights can be made smaller or set to zero without affecting the communicability significantly. [ABSTRACT FROM AUTHOR]

Traces of inverse powers of a positive definite symmetric tridiagonal matrix give lower bounds of the minimal singular value of an upper bidiagonal matrix. In a preceding work, a formula for the traces which gives the diagonal entries of the inverse powers is presented. In this paper, we present another formula which gives the traces based on a quite different idea from the one in the preceding work. An efficient implementation of the formula for practice is also presented. [ABSTRACT FROM AUTHOR]

In this work, we consider symmetric positive definite pencils depending on two parameters. That is, we are concerned with the generalized eigenvalue problem A (x) − λ B (x) v = 0 , where A and B are symmetric matrix valued functions in ℝ n × n , smoothly depending on parameters x ∈ Ω ⊂ ℝ 2 ; furthermore, B is also positive definite. In general, the eigenvalues of this multiparameter problem will not be smooth, the lack of smoothness resulting from eigenvalues being equal at some parameter values (conical intersections). Our main goal is precisely that of locating parameter values where eigenvalues are equal. We first give general theoretical results for the present generalized eigenvalue problem, and then introduce and implement numerical methods apt at detecting conical intersections. Finally, we perform a numerical study of the statistical properties of coalescing eigenvalues for pencils where A and B are either full or banded, for several bandwidths. [ABSTRACT FROM AUTHOR]

In this paper, based on the two-step Newton iterative procedure, we propose a two-step inexact Newton-type method for solving inverse singular value problems. Under some mild assumptions, our results show that the two-step inexact Newton-type method is super quadratically convergent. Numerical implementations demonstrate the effectiveness of the new method. [ABSTRACT FROM AUTHOR]

Inthis paper, we study the global uniqueness and solvability of tensor complementarity problems for ℋ + -tensors. We obtain a sufficient condition of the global uniqueness and solvability of tensor complementarity problems for ℋ + -tensors. We present nonlinear dynamical system models for solving the tensor complementarity problem (TCP). We prove that the presented dynamical system models are stable in the sense of Lyapunov stability theory for considering three classes of structured tensors. The computer simulation results further substantiate that the considered dynamical system can be used to solve the TCP. [ABSTRACT FROM AUTHOR]

A randomized quaternion singular value decomposition algorithm based on block Krylov iteration (RQSVD-BKI) is presented to solve the low-rank quaternion matrix approximation problem. The upper bounds of deterministic approximation error and expected approximation error for the RQSVD-BKI algorithm are also given. It is shown by numerical experiments that the running time of the RQSVD-BKI algorithm is smaller than that of the quaternion singular value decomposition, and the relative errors of the RQSVD-BKI algorithm are smaller than those of the randomized quaternion singular value decomposition algorithm in Liu et al. (SIAM J. Sci. Comput., 44(2): A870-A900 (2022)) in some cases. In order to further illustrate the feasibility and effectiveness of the RQSVD-BKI algorithm, we use it to deal with the problem of color image inpainting. [ABSTRACT FROM AUTHOR]

The strong ℋ -tensors have important applications in many areas of science and engineering, e.g., the determination of positive definiteness for an even-order homogeneous polynomial form in the real field. In this paper, we propose two iterative algorithms with non-parameter for identifying strong ℋ -tensors, which overcome the drawback of choosing the best value of parameter 𝜖 in some existing algorithms given by Li et al. and Liu et al. (J. Comput. Appl. Math., 255, 1–14, 2014 and Comput. Appl. Math. 36, 1623–1635, 2017). Some numerical experiments are performed to illustrate the feasibility and effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

This paper deals with generalized centro-invertible matrices introduced by the authors in Lebtahi et al. (Appl. Math. Lett. 38, 106-109, 2014). As a first result, we state the coordinability between the classes of involutory matrices, generalized centro-invertible matrices, and {K}-centrosymmetric matrices. Then, some characterizations of generalized centro-invertible matrices are obtained. A spectral study of generalized centro-invertible matrices is given. In addition, we prove that the sign of a generalized centro-invertible matrix is {K}-centrosymmetric and that the class of generalized centro-invertible matrices is closed under the matrix sign function. Finally, some algorithms have been developed for the construction of generalized centro-invertible matrices. [ABSTRACT FROM AUTHOR]

An interesting problem was raised in Vong et al. (SIAM J. Matrix Anal. Appl. 32:412-429, 2011): whether the Ulm-like method and its convergence result can be extended to the cases of multiple and zero singular values. In this paper, we study the convergence of a Ulm-like method for solving the square inverse singular value problem with multiple and zero singular values. Under the nonsingularity assumption in terms of the relative generalized Jacobian matrices, a convergence analysis for the multiple and zero case is provided and the quadratical convergence property is proved. Moreover, numerical experiments are given in the last section to demonstrate our theoretic results. [ABSTRACT FROM AUTHOR]

In this paper, we generalize the algorithm described by Rump and Graillat to compute verified and narrow error bounds such that a slightly perturbed matrix is guaranteed to have an eigenvalue with geometric multiplicity q within computed error bounds. The corresponding invariant subspace can be directly obtained by our algorithm. Our verification method is based on border matrix technique. We demonstrate the performance of our algorithm for matrices of dimension up to hundreds with non-defective and defective eigenvalues. [ABSTRACT FROM AUTHOR]

The Cauchy radius of a scalar polynomial is an upper bound on the magnitude of its zeros, and it is optimal among all bounds depending only on the moduli of the coefficients. It has the disadvantage of being implicit because it requires the solution of a nonlinear equation. In this note, simple and explicit upper bounds are derived that are useful approximations to the Cauchy radius. The general approach to obtain the aforementioned bounds is to embed scalar polynomials into the larger framework of their generalization to matrix polynomials and then use bounds on the eigenvalues of the latter. [ABSTRACT FROM AUTHOR]

In this paper, the singular value decompositions of anti-symmetric matrices and anti-bisymmetric matrices are presented, and a class of parameterized inverse singular value problem for anti-bisymmetric matrices is solved. Numerical examples which confirm our theory are presented. [ABSTRACT FROM AUTHOR]

Convergence of the implicitly restarted Arnoldi (IRA) method for nonsymmetric eigenvalue problems has often been studied by deriving bounds for the angle between a desired eigenvector and the Krylov projection subspace. Bounds for residual norms of approximate eigenvectors have been less studied and this paper derives a new a-posteriori residual bound for nonsymmetric matrices with simple eigenvalues. The residual vector is shown to be a linear combination of exact eigenvectors and a residual bound is obtained as the sum of the magnitudes of the coefficients of the eigenvectors. We numerically illustrate that the convergence of the residual norm to zero is governed by a scalar term, namely the last element of the wanted eigenvector of the projected matrix. Both cases of convergence and non-convergence are illustrated and this validates our theoretical results. We derive an analogous result for implicitly restarted refined Arnoldi (IRRA) and for this algorithm, we numerically illustrate that convergence is governed by two scalar terms appearing in the linear combination which drives the residual norm to zero. We provide a set of numerical results that validate the residual bounds for both variants of Arnoldi methods. [ABSTRACT FROM AUTHOR]

Estimates for the condition number of a matrix are useful in many areas of scientific computing, including: recursive least squares computations, optimization, eigenanalysis, and general nonlinear problems solved by linearization techniques where matrix modification techniques are used. The purpose of this paper is to propose an adaptive Lanczos estimator scheme, which we call ale, for tracking the condition number of the modified matrix over time. Applications to recursive least squares (RLS) computations using the covariance method with sliding data windows are considered. ale is fast for relatively small n-parameter problems arising in RLS methods in control and signal processing, and is adaptive over time, i.e., estimates at time t are used to produce estimates at time t+1. Comparisons are made with other adaptive and non-adaptive condition estimators for recursive least squares problems. Numerical experiments are reported indicating that ale yields a very accurate recursive condition estimator. [ABSTRACT FROM AUTHOR]

We investigate contour integral-based eigensolvers for computing all eigenvalues located in a certain region and their corresponding eigenvectors. In this paper, we focus on a Rayleigh-Ritz type method and analyze its error bounds. From the results of our analysis, we conclude that the Rayleigh-Ritz type contour integral-based eigensolver with sufficient subspace size can achieve high accuracy for target eigenpairs even if some eigenvalues exist outside but near the region. [ABSTRACT FROM AUTHOR]

Motivated by the Cadzow filtering in seismic data processing, this paper presents a fast SVD method for multilevel block Hankel matrices. A seismic data presented as a multidimensional array is first transformed into a two dimensional multilevel block Hankel (MBH) matrix. Then the Lanczos process is applied to reduce the MBH matrix into a bidiagonal or tridiagonal matrix. Finally, the SVD of the reduced matrix is computed using the twisted factorization method. To achieve high efficiency, we propose a novel fast MBH matrix-vector multiplication method for the Lanczos process. In comparison with existing fast Hankel matrix-vector multiplication methods, our method applies 1-D, instead of multidimensional, FFT and requires minimum storage. Moreover, a partial SVD is performed on the reduced matrix, since complete SVD is not required by the Caszow filtering. Our numerical experiments show that our fast MBH matrix-vector multiplication method significantly improves both the computational cost and storage requirement. Our fast MBH SVD algorithm is particularly efficient for large size multilevel block Hankel matrices. [ABSTRACT FROM AUTHOR]

In this paper a particular partition on blocks of generalized ( h, r)-circulant matrices is determined. We obtain a characterization of generalized ( h, r)-circulant matrices and get some results on the values of the permanent and also on the determination of the eigenvalues of r-circulant matrices. At last, a lower bound for the permanent of these matrices is achieved. [ABSTRACT FROM AUTHOR]

The LSQR iterative method for solving least-squares problems may require many iterations to determine an approximate solution with desired accuracy. This often depends on the fact that singular vector components of the solution associated with small singular values of the matrix require many iterations to be determined. Augmentation of Krylov subspaces with harmonic Ritz vectors often makes it possible to determine the singular vectors associated with small singular values with fewer iterations than without augmentation. This paper describes how Krylov subspaces generated by the LSQR iterative method can be conveniently augmented with harmonic Ritz vectors. Computed examples illustrate the competitiveness of the augmented LSQR method proposed. [ABSTRACT FROM AUTHOR]

The eigenvalue localization problem is very closely related to the $H$-matrix theory. The most elegant example of this relation is the equivalence between the Geršgorin theorem and the theorem about nonsingularity of SDD (strictly diagonally dominant) matrices, which is a starting point for further beautiful results in the book of Varga []. Furthermore, the corresponding Geršgorin-type theorem is equivalent to the statement that each matrix from a particular subclass of $H$-matrices is nonsingular. Finally, the statement that all eigenvalues of a given matrix belong to minimal Geršgorin set (defined in []) is equivalent to the statement that every $H$-matrix is nonsingular. Since minimal Geršgorin set remained unattainable, a lot of different Geršgorin-type areas for eigenvalues has been developed recently. Along with them, a lot of new subclasses of $H$-matrices were obtained. A survey of recent results in both areas, as well as their relationships, will be presented in this paper. [ABSTRACT FROM AUTHOR]

Complex symmetric matrices often appear in quantum physics in the solution methods of partial differential equations such as the Schrödinger equation. We have recently introduced a new fast and efficient direct eigensolver for this problem in [4], and reported its performance in the eigenvalue calculation in [3]. In this paper, we further report on some benchmark tests for computing the full and partial eigenspectrum on a variety of super computing machines, i.e., the Cray J-932, the DEC Alfa 8400, and the SGI Power Challenge 8000 and 10000. We observe that in all cases the new algorithm is much faster than codes available in standard state of the art eigensolver packages such as LAPACK. [ABSTRACT FROM AUTHOR]

A quasi-Toeplitz (QT) matrix is a semi-infinite matrix of the form A = T (a) + E where T(a) is the Toeplitz matrix with entries (T (a)) i , j = a j - i , for a j - i ∈ C , i , j ≥ 1 , while E is a matrix representing a compact operator in ℓ 2 . The matrix A is finitely representable if a k = 0 for k < - m and for k > n , given m , n > 0 , and if E has a finite number of nonzero entries. The problem of numerically computing eigenpairs of a finitely representable QT matrix is investigated, i.e., pairs (λ , v) such that A v = λ v , with λ ∈ C , v = (v j) j ∈ Z + , v ≠ 0 , and ∑ j = 1 ∞ | v j | 2 < ∞ . It is shown that the problem is reduced to a finite nonlinear eigenvalue problem of the kind W U (λ) β = 0 , where W is a constant matrix and U depends on λ and can be given in terms of either a Vandermonde matrix or a companion matrix. Algorithms relying on Newton's method applied to the equation det W U (λ) = 0 are analyzed. Numerical experiments show the effectiveness of this approach. The algorithms have been included in the CQT-Toolbox [Numer. Algorithms 81 (2019), no. 2, 741–769]. [ABSTRACT FROM AUTHOR]

A new class of tensors called K S -tensors, which is a subset of non-singular P -tensors and generalization of H + -tensors, is proposed. It is proved that the system of K S -tensor equations always has a unique positive solution for any positive right-hand side by proposing a positive increasing map. Two approaches based on dynamical system are presented to find the unique positive solution. The theoretical analysis results show that the convergence of the proposed models is guaranteed, and numerical examples further illustrate that the given models are feasible and effective in finding the positive solution of K S -tensor equations. [ABSTRACT FROM AUTHOR]

The joint bidiagonalization (JBD) process is a useful algorithm for the computation of the generalized singular value decomposition (GSVD) of a matrix pair. However, it always suffers from rounding errors, which causes the Lanczos vectors to lose their mutual orthogonality. In order to maintain some level of orthogonality, we present a semiorthogonalization strategy. Our rounding error analysis shows that the JBD process with the semiorthogonalization strategy can ensure that the convergence of the computed quantities is not affected by rounding errors and the final accuracy is high enough. Based on the semiorthogonalization strategy, we develop the joint bidiagonalization process with partial reorthogonalization (JBDPRO). In the JBDPRO algorithm, reorthogonalizations occur only when necessary, which saves a big amount of reorthogonalization work, compared with the full reorthogonalization strategy. Numerical experiments illustrate our theory and algorithm. [ABSTRACT FROM AUTHOR]

The Iterative Filtering method is a technique developed recently for the decomposition and analysis of nonstationary and nonlinear signals. In this work, we propose two alternative formulations of the original algorithm which allows to transform the iterative filtering method into a direct technique, making the algorithm closer to an online algorithm. We present a few numerical examples to show the effectiveness of the proposed approaches. [ABSTRACT FROM AUTHOR]

A self-adaptive trust region method is presented for finding the largest or smallest ℬ -eigenvalues of symmetric tensors. One of the important features of this method is that ℬ -eigenvalues problem of symmetric tensors is transformed into a homogenous polynomial optimization. Global convergence of the proposed algorithm and second-order necessary conditions of the optimal solutions are established, respectively. Numerical experiments are listed to illustrate the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

In this work, we develop and implement new numerical methods to locate generic degeneracies (i.e., isolated parameters' values where the eigenvalues coalesce) of banded matrix valued functions. More precisely, our specific interest is in two classes of problems: (i) symmetric, banded, functions A(x) ∈ ℝn×n, smoothly depending on parameters x ∈ Ω ⊂ ℝ2 and (ii) Hermitian, banded, functions A(x) ∈ ℂn×n, smoothly depending on parameters x ∈Ω⊂ ℝ3. The computational task of detecting coalescing points of banded parameter-dependent matrices is very delicate and challenging and cannot be handled using existing eigenvalues' continuation approaches. For this reason, we present and justify new techniques that will enable continuing path of eigendecompositions and reliably decide whether or not eigenvalues coalesce, well beyond our ability to numerically distinguish close eigenvalues. As important motivation, and illustration, of our methods, we perform a computational study of the density of coalescing points for random ensembles of banded matrices depending on parameters. Relatively to random matrix models from truncated GOE and GUE ensembles, we will give computational evidence in support of power laws for coalescing points, expressed in terms of the size and bandwidth of the matrices. [ABSTRACT FROM AUTHOR]

A new Brauer-type Z-eigenvalue inclusion set for tensors is given and proved to be tighter than those in Wang et al. (Discrete Contin. Dyn. Syst., Ser. B. 22(1), 187-198, 2017). Based on this set, a sharper upper bound for the Z-spectral radius of weakly symmetric nonnegative tensors is obtained. Numerical examples are reported to verify the theoretical results. [ABSTRACT FROM AUTHOR]

Any symmetric matrix can be reduced to antitriangular form in finitely many steps by orthogonal similarity transformations. This form reveals the inertia of the matrix and has found applications in, e.g., model predictive control and constraint preconditioning. Originally proposed by Mastronardi and Van Dooren, the existing algorithm for performing the reduction to antitriangular form is primarily based on Householder reflectors and Givens rotations. The poor memory access pattern of these operations implies that the performance of the algorithm is bound by the memory bandwidth. In this work, we develop a block algorithm that performs all operations almost entirely in terms of level 3 BLAS operations, which feature a more favorable memory access pattern and lead to better performance. These performance gains are confirmed by numerical experiments that cover a wide range of different inertia. [ABSTRACT FROM AUTHOR]