Fast algorithms for hierarchically semiseparable matrices

Semiseparable matrices and many other rank‐structured matrices have been widely used in developing new fast matrix algorithms. In this paper, we generalize the hierarchically semiseparable (HSS) matrix representations and propose some fast algorithms for HSS matrices. We represent HSS matrices in terms of general binary HSS trees and use simplified postordering notation for HSS forms. Fast HSS algorithms including new HSS structure generation and HSS form Cholesky factorization are developed. Moreover, we provide a new linear complexity explicit ULV factorization algorithm for symmetric positive definite HSS matrices with a low‐rank property. The corresponding factors can be used to solve the HSS systems also in linear complexity. Numerical examples demonstrate the efficiency of the algorithms. All these algorithms have nice data locality. They are useful in developing fast‐structured numerical methods for large discretized PDEs (such as elliptic equations), integral equations, eigenvalue problems, etc. Some applications are shown. Copyright © 2009 John Wiley & Sons, Ltd.     

New fast divide‐and‐conquer algorithms for the symmetric tridiagonal eigenvalue problem

In this paper, two accelerated divide‐and‐conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N²r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy‐like matrices and are off‐diagonally low‐rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low‐rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off‐diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. Copyright © 2016 John Wiley & Sons, Ltd.     

ON HERMITIAN AND SKEW-HERMITIAN SPLITTING ITERATION METHODS FOR CONTINUOUS SYLVESTER EQUATIONS

We present a Hermitian and skew-Hermitian splitting (HSS) iteration method for solving large sparse continuous Sylvester equations with non-Hermitian and positive definite/semi-definite matrices. The unconditional convergence of the HSS iteration method is proved and an upper bound on the convergence rate is derived. Moreover, to reduce the computing cost, we establish an inexact variant of the HSS iteration method and analyze its convergence property in detail. Numerical results show that the HSS iteration method and its inexact variant are efficient and robust solvers for this class of continuous Sylvester equations.     

Semilocal and global convergence of the Newton‐HSS method for systems of nonlinear equations

Newton‐HSS methods, which are variants of inexact Newton methods different from the Newton–Krylov methods, have been shown to be competitive methods for solving large sparse systems of nonlinear equations with positive‐definite Jacobian matrices (J. Comp. Math. 2010; 28 :235–260). In that paper, only local convergence was proved. In this paper, we prove a Kantorovich‐type semilocal convergence. Then we introduce Newton‐HSS methods with a backtracking strategy and analyse their global convergence. Finally, these globally convergent Newton‐HSS methods are shown to work well on several typical examples using different forcing terms to stop the inner iterations. Copyright © 2010 John Wiley & Sons, Ltd.     

Convergence analysis of modified Newton-HSS method for solving systems of nonlinear equations

Hermitian and skew-Hermitian splitting(HSS) method has been proved quite successfully in solving large sparse non-Hermitian positive definite systems of linear equations. Recently, by making use of HSS method as inner iteration, Newton-HSS method for solving the systems of nonlinear equations with non-Hermitian positive definite Jacobian matrices has been proposed by Bai and Guo. It has shown that the Newton-HSS method outperforms the Newton-USOR and the Newton-GMRES iteration methods. In this paper, a class of modified Newton-HSS methods for solving large systems of nonlinear equations is discussed. In our method, the modified Newton method with R-order of convergence three at least is used to solve the nonlinear equations, and the HSS method is applied to approximately solve the Newton equations. For this class of inexact Newton methods, local and semilocal convergence theorems are proved under suitable conditions. Moreover, a globally convergent modified Newton-HSS method is introduced and a basic global convergence theorem is proved. Numerical results are given to confirm the effectiveness of our method.     

Fine Spectra of Tridiagonal Toeplitz Matrices

Ukrainian Mathematical Journal - The fine spectra of n-banded triangular Toeplitz matrices and (2n+1)-banded symmetric Toeplitz matrices were computed in (M. Altun, Appl. Math. Comput., 217,...     

Skew-adjacency matrices of graphs

The spectra of the skew-adjacency matrices of a graph are considered as a possible way to distinguish adjacency cospectral graphs. This leads to the following topics: graphs whose skew-adjacency matrices are all cospectral; relations between the matchings polynomial of a graph and the characteristic polynomials of its adjacency and skew-adjacency matrices; skew-spectral radii and an analogue of the Perron–Frobenius theorem; and, the number of skew-adjacency matrices of a graph with distinct spectra.     

Preparation and optical properties of GaSb nanoparticles embedded in SiO2 composite films

The composite films of GaSb nanoparticles embedded in SiO₂ matrices were fabricated by radio-frequency magnetron co-sputtering. Transmission electron microscope and X-ray diffraction pattern indicate that the GaSb nanoparticles were uniformly dispersed in SiO₂ matrices. Room temperature transmission spectra exhibit a blue shift of about 2.73 eV. The blue shift increases with decreasing size of GaSb nanoparticles, suggesting the existence of quantum size effects. Room temperature Raman spectra show that there is a larger Raman peak red shift and broadening of the composite films than that of bulk GaSb. This phenomenon is explained by photon confinement effect and tensile stress effect     

To solving spectral problems for <Emphasis Type="Italic">q</Emphasis>-parameter polynomial matrices

The method of hereditary pencils, originally suggested by the author for solving spectral problems for two-parameter matrices (pencils of matrices), is extended to the case of q-parameter, q ≥ 2, polynomial matrices. Algorithms for computing points of the finite regular and singular spectra of a q-parameter polynomial matrix and their theoretical justification are presented. Bibliography: 2 titles.     

Preparation and optical properties of GaSb nanoparticles embedded in SiO2 composite films

The composite films of GaSb nanoparticles embedded in SiO₂ matrices were fabricated by radio-frequency magnetron co-sputtering. Transmission electron microscope and X-ray diffraction pattern indicate that the GaSb nanoparticles were uniformly dispersed in SiO₂ matrices. Room temperature transmission spectra exhibit a blue shift of about 2.73 eV. The blue shift increases with decreasing size of GaSb nanoparticles, suggesting the existence of quantum size effects. Room temperature Raman spectra show that there is a larger Raman peak red shift and broadening of the composite films than that of bulk GaSb. This phenomenon is explained by photon confinement effect and tensile stress effect     

Fine spectra of upper triangular double-band matrices

The fine spectra of lower triangular double-band matrices have been examined by several authors (e.g. [13] and [22]). Here we determine the fine spectra of upper triangular double-band matrices over the sequence spaces c₀ and c. Upper triangular double-band matrices are infinite matrices which include the left-shift, averaging and difference operators.     

环F2+vF2上线性码的深度谱

本文研究了环R=F2+vF2上线性码的深度分布和深度谱.利用环R到F2加群的两个同态映射及R上线性码的生成矩阵,给出了环R上4k12k22k3型线性码的深度谱的上下界.     

Discrete and Cantor Spectrum for Neumann Laplacians of Combs

Extending results of [HSS] on the construction of Neumann Laplacians of combs with given essential spectrum S = S [0,∞], we show that, in addition to the essential spectrum, a bounded sequence of discrete eigenvalues can be prescribed. More generally, we find that certain types of spectra can be constructed precisely, in a bounded interval [0, s].     

On the accelerated modified Newton-HSS method for systems of nonlinear equations

Hermitian and skew-Hermitian splitting (HSS) method converges unconditionally, which is efficient and robust for solving non-Hermitian positive-definite systems of linear equations. For solving systems of nonlinear equations with non-Hermitian positive-definite Jacobian matrices, Bai and Guo proposed the Newton-HSS method and gave numerical comparisons to show that the Newton-HSS method is superior to the Newton-USOR, the Newton-GMRES and the Newton-GCG methods. Recently, Wu and Chen proposed the modified Newton-HSS (MN-HSS) method which outperformed the Newton-HSS method. In this paper, we will establish a new accelerated modified Newton-HSS (AMN-HSS) method and give the local convergence theorem. Moreover, numerical results show that the AMN-HSS method outperforms the MN-HSS method.     

Generalization of some results concerning eigenvalues of a certain class of matrices and some applications

In this note, we present a generalization of some results concerning the spectral properties of a certain class of block matrices. As applications, we study some of its implications on nonnegative matrices and doubly stochastic matrices as well as on graph spectra and graph energy.     

关于广义鞍点问题的HSS迭代方法的收缩因子(英文)

白中治等提出了解非埃尔米特正定线性方程组的埃尔米特和反埃尔米特分裂(HSS)迭代方法(Bai Z Z,Golub G H,Ng M K.Hermitian and skew-Hermitian splitting methodsfor non-Hermitian positive definite linear systems.SIAM J.Matrix Anal.Appl.,2003,24:603-626).本文精确地估计了用HSS迭代方法求解广义鞍点问题时在加权2-范数和2-范数下的收缩因子.在实际的计算中,正是这些收缩因子而不是迭代矩阵的谱半径,本质上控制着HSS迭代方法的实际收敛速度.根据文中的分析,求解广义鞍点问题的HSS迭代方法的收缩因子在加权2-范数下等于1,在2-范数下它会大于等于1,而在某种适当选取的范数之下,它则会小于1.最后,用数值算例说明了理论结果的正确性.     

缺项3×3上三角算子矩阵的可能谱

根据值域的稠密性和闭性,可将有界线性算子的点谱和剩余谱进一步细分为1,2-类点谱和1,2-类剩余谱.针对3×3阶上三角算子矩阵,采用分析方法和空间分解方法分别刻画了可能1,2-类点谱和可能1,2-类剩余谱.     

De Toda à KdV

We consider the large number of particles limit of a periodic Toda lattice for a family of initial data close to the equilibrium state. We show that each of the two edges of the spectra of the corresponding Jacobi matrices is up to an error, determined by the spectra of two Hill operators, associated to this family. We then show that the spectra of the Jacobi matrices remain almost constant when the matrices evolve along the two limiting KdV equations. Finally we prove that the Toda actions, when appropriately renormalized, converge to the ones of KdV. To cite this article: D. Bambusi et al., C. R. Acad. Sci. Paris, Ser. I 347 (2009).     

ON NEWTON-HSS METHODS FOR SYSTEMS OF NONLINEAR EQUATIONS WITH POSITIVE-DEFINITE JACOBIAN MATRICES

The Hermitian and skew-Hermitian splitting （HSS） method is an unconditionally convergent iteration method for solving large sparse non-Hermitian positive definite system of linear equations. By making use of the HSS iteration as the inner solver for the Newton method, we establish a class of Newton-HSS methods for solving large sparse systems of nonlinear equations with positive definite Jacobian matrices at the solution points. For this class of inexact Newton methods, two types of local convergence theorems are proved under proper conditions, and numerical results are given to examine their feasibility and effectiveness. In addition, the advantages of the Newton-HSS methods over the Newton-USOR, the Newton-GMRES and the Newton-GCG methods are shown through solving systems of nonlinear equations arising from the finite difference discretization of a two-dimensional convection-diffusion equation perturbed by a nonlinear term. The numerical implemen- tations also show that as preconditioners for the Newton-GMRES and the Newton-GCG methods the HSS iteration outperforms the USOR iteration in both computing time and iteration step.     

Spectra and Fine Spectra for Factorable Matrices

We obtain the spectra and fine spectra for factorable triangular matrices. Our results contain some previous work of the authors as special cases.