Randomized Iterative Algorithms For Two Kinds Of Linear System Of Equations And Shift-and-invert Arnoldi Algorithm For Chemical Master Equation

Solving large sparse linear system of equations and computing large-scale matrix exponential function remain the key ingredient for problems from both scientific computation and artificial intelligence,and contriving efficient solvers for these two kinds of problems maintains one of the most-studied research area in linear algebra.In the present thesis,we extend the greedy randomized Kaczmarz algorithm and greedy randomized Gauss-Seidel algorithm to both ridge regression and factorized linear systems and construct the corresponding relaxed randomized iterative algorithm;on the other hand,by using the shift-and-invert technique and reorthogonalization Arnoldi procedure,we propose a new numerical algorithm(SIRA)to approximate the exact solution(the product of a matrix with a vector)of the chemical master equation.The main contributions are as follows:1.For ridge regression,considering that the coefficient matrix of its normal equation is symmetric positive definite,we first modify the probability criterion and iterative formula of the GRK algorithm by using the properties of symmetric positive definite matrix,and establish the corresponding convergence theory for the resulting algorithm,that is,a variant of GRK algorithm.We then introduce relaxation parameter lies in the interval(0,2)in the update rule of the variant of GRK algorithm,and obtain a relaxed version of this algorithm for ridge regression and prove its convergence.Furthermore,in order to use the residual vector with respect to the normal equation of the ridge regression at each iteration step as far as possible,we propose an accelerated scheme of the relaxed variant of GRK algorithm.Numerical experiments show that the convergence rates of the three algorithms proposed in this paper are obviously faster than that of the algorithms discussed in [51],and the variant of GRK algorithm with relaxation and its accelerated scheme cost much less CPU time.2.Both RK-RK and REK-RK are the latest randomized iterative algorithms for solving factorized linear systems.Considering the fast convergence of both GRK and GRGS algorithms,we construct relaxed GRK-GRK algorithm and GRGS-GRK algorithm for consistent and inconsistent factorized linear systems,respectively,and establish the corresponding convergence theory for these two algorithms.Numerical experiments show that our proposed algorithms perform much better than RK-RK and REK-RK algorithms in both iteration steps and CPU times for factorized linear systems.3.Both FSP and Krylov FSP are two classical reduction algorithms for solving the chemical master equation(CME)at present.In this thesis,by using the shift-and-invert technique and reorthogonalization Arnoldi procedure,we construct a SIRA algorithm for approximating the exact solution of the chemical master equation,which does not need to determine the initial finite state projection set and its expansion method,so the calculation process is simple.Numerical experiments on specific biochemical reaction systems show that the SIRA algorithm is more accuracy than both the FSP and Krylov FSP algorithms in terms of medium-sized CME.