The Study Of Numerical Methods For Solving Generank Problem

Matrix computation is the foundation of scientific and engineering computing.Many scientific and engineering computing problems usually will be reduced to bethe corresponding matrix computation problems. In molecular biology, when westudy the gene expression, we find that there are many genes in a sequence but onlyfew of them play a significant role in gene expression, and these genes also play adifferent role. So how to find the important genes from the sequence and rank thesegenes in order of importance is an important task. In2005, a new mathematical modelabout this problem, which is called GeneRank, was proposed by Morrison et al.The GeneRank problem is usually reduced to the eigenvalue problem with thelarge unsymmetrical matrix or the solution of the unsymmetrical system of linearequations. The matrix in GeneRank problem is very huge, and the general iterationmethods for solving eigenvalue have many defects, such as convergence rate is slow,computational complexity and time complexity are too large, such as Jacobi iteration,Gauss-Seidel iterative method or power method. However, as well known, Krylovsubspace methods maybe are effective for solving GeneRank problem, becauseKrylov subspace methods can reduce the original problem to a smaller problem bychoosing appropriate Krylov subspace.This paper mainly studies the algorithm for solving the GeneRank problem. Asthis problem is a new topic, the high-performance algorithm for solving this problemis still on-going. But as the GeneRank problem and the PageRank problem are veryanalogical, the algorithms for solving the PageRank problem can be extended to solvethe GeneRank problem. In this dissertation, the Arnoldi-type algorithm for solving thePageRank problem is extended to solve the GeneRank problem, by combining withthe existing ones. Firstly, in this paper, we modify the Arnoldi-type algorithm forsolving the GeneRank problem using the residual vector which comes from eachiteration. According to the features of the Arnoldi-type algorithm, making the best ofthe residual vector will effectively improve the convergence rate and reduce thenumber of iterations. Secondly, we modify the Arnoldi-type algorithm for solving the GeneRank problem by using two vectors, which are the residual vectors producedfrom each iteration and the (m+1)-th orthogonal vector produced by the m-th step ofArnoldi algorithm. Finally, numerical experiments are given to show the efficiency ofnew methods.