论文部分内容阅读
矩阵计算是科学和工程计算的基础,很多科学和工程计算的问题往往最终都是转化为矩阵计算问题来获得所要求的数值结果。在分子生物学中,研究基因表达时发现,在一个基因列表内的成千上万的基因中,发挥作用的只有少数的基因,并且这少数基因发挥作用的大小也不同,因此,发掘每个基因的重要性并且对重要性进行排序就有着重要的价值。针对这个问题,2005年莫里森等人提出了一个新的模型叫做GeneRank,即基因排序模型。GeneRank问题往往转化为求解一个大型非对称随机矩阵的特征值问题或者是大型非对称的线性方程组。在GeneRank问题中涉及的矩阵阶数巨大,通常的线性方程组的迭代算法或者求解特征值的方法存在着收敛速度慢,存储过大,计算量过大等问题。例如用雅可比,高斯-赛德迭代,幂法等求解GeneRank问题存在着收敛速度过慢,计算量巨大的问题。众所周知,Krylov子空间方法通过选取适当子空间,将原问题转变为求解一个更小规模的问题,如Arnoldi-型算法。本文主要研究GeneRank问题的求解算法。迄今为止,高效的求解算法还不多。然而,由于GeneRank问题与PageRank问题有很大程度的相似,因此我们可以推广求解PageRank问题的算法到GeneRank问题。本文主要推广了求解PageRank问题的Arnoldi-型算法,并对此算法进行优化。优化过程首先考虑利用每一步迭代的参量去优化求解GeneRank问题的Arnoldi-型算法。根据Arnoldi-型算法的迭代特点,能充分利用每一步迭代产生的残量,有效的加快收敛并降低需要的迭代次数。其次结合已有的利用m次迭代的Arnoldi算法每一步迭代的第m+1个正交向量优化求解解GeneRank问题的Arnoldi-型算法,充分利用每一步迭代产生的参量和正交向量,得到了一个更高效的算法。数值实验验证了新方法的有效性。