Stochastic Solving Algorithms For Systems Of Linear Equations And Eigenvalue Decomposition Of Low-precision Matrices

Linear system is an important problem in numerical algebra.Although there are many algorithms that are well developed,for large-scale system or with specific demands,the corresponding algorithm still needs to studied.Many problems can be transformed into linear systems to get an easy solution,and vice versa.We transform large-scale linear system into convex feasibility problem,and linear system with Hermitian matrix at low precision into Hermitian matrix eigendecomposition problem.For the former one,we combine the randomization idea for Kaczmarz with Douglas-Rachford method.We finish the proof of convergence in sense of expecta-tion for randomized Douglas-Rachford method.It shows that randomized Douglas-Rachford method has similar rate of convergence as randomized Kaczmarz method in numerical experiment.For the latter one,classic algorithm contains three steps which are Lanczos tridiagonalization,Sturm dichotomy and inverse power method.In this article,we consider the Hermitian matrix eigendecomposition problem of small size at low precision.We use selective reorthogonalization to lower the error for Lanczos tridi-agonalization.And iterative refinement is applied to improve the precision of inverse power method.It shows that these improvements do improve the accuracy of tra-ditional scheme in numerical experiment.