Some Fast Algorithms Based On Structured Matrix Techniques And Their Applications

Efficient and reliable rank-structured matrix computations have been an intensive focus of recent research. Rank-structured matrices include semiseparable, quasiseparable,sequentially semiseparable(SSS), hierarchically semiseparable(HSS), H,H2matrices,etc. They have been used for solving Toeplitz, Cauchy linear equations, the zeros of polynomials, integral equations, singular value and eigenvalue problems. Recently, they also have been shown to play central roles in solving large sparse linear equations. In this thesis we propose three types of fast algorithms:(dense) rank-structured matrix factorizations, eigenvalue and singular value problems and root finders of nonlinear equations.Most of these algorithms are based on HSS matrix techniques, and numerous experiments have been done to shown their efficiency. The context can be divided into three parts.In the first part(Chap. 2–3), we propose two new fast and robust factorization algorithms for HSS matrices, generalized Cholesky factorization for symmetric positive definite HSS matrices and generalized LU factorization for general HSS matrices. Different from previous algorithms, the newly proposed algorithms use a strategy involving orthogonal transformations and approximations which avoids the explicit computation of Schur complement in each factorization step. It makes our algorithms have good data locality and require fewer floating point operations. Furthermore, we propose a modified compression method for the generalized LU factorization when some diagonal blocks are ill-conditioned. A randomized SVD algorithm is used to compute the low-rank approximations, which is shown to be very fast and numerically stable with quite high probability.Both these two factorizations can be used for solving integral equations, PDEs, and developing direct solvers or preconditioners for large sparse linear equations. Numerical results show the efficiency of our algorithms.In the second part(Chap. 4–6), some fast algorithms are developed for eigenvalue problems, such as updating SVD, bidiagonal SVD and tridiagonal eigenvalue problems.The main point is that some Cauchy-like matrices appeared in some classical algorithms are rank-structured matrices. If use HSS matrices to approximate them and then use HSS matrix multiplications to compute the singular vectors or eigenvectors, it can save a lot of flops. We modify an HSS construction algorithm for Cauchy-like matrices, which only needs O(N) memory(N is the dimension of matrix), and therefore it can deal with larger matrices than other HSS construction algorithms. All the these techniques together make our algorithms be more than 3x times faster than Intel MKL for some very large matrices without any loss of accuracy.In the third part(Chap. 7–8), we propose an improved dqds algorithm for computing all the singular values of bidiagonal matrices, and some high-order Newton’s methods for nonlinear equations. The eigenvalue(singular value) problems are highly related to the roots of polynomials, which is also the motivation for working on root finders. There are two key contributions in our improved dqds algorithm: a novel deflation strategy(called d-deflation strategy) that improves the convergence for disordered matrices, and some modifications to certain shift strategies that accelerate the convergence for most bidiagonal matrices. Our extensive numerical experiments indicate that our improved dqds(denoted by V5) is typically 1.2x–4x faster than DLASQ(the LAPACK-3.4.0implementation of dqds) without any degradation in accuracy. On matrices for which DLASQ shows very slow convergence, V5 can be 3x–10x faster. The d-deflation strategy has been implemented in LAPACK-3.4.1. A hybrid algorithm(HDLASQ) is obtained by combining V5 with the aggressive early deflation strategy, which is shown to be 70 x times faster than DLASQ for some particular matrices. In Chapter 8, we propose some third and fourth order Newton’s methods for nonlinear equations, which converge much faster than the classical Newton’s methods(order of 2). The convergence rates of these algorithms have been proved. Chapter 9 summarizes the main contributions of this dissertation and some future works to be done.