大型稀疏矩阵线形相关列的求解算法和实现方法研究  

RESEARCH ON THE ALGORTHM FOR FINDING LINEAR DEPENDENCE IN LARGE SPARSE MATRICES AND ITS IMPLEMENTATION METHOD

作　　者：褚一平[1] 陈勤[1] 吴铤[1] 

机构地区：[1]杭州电子工业学院软件学院,杭州310018

出　　处：《石油工业计算机应用》2004年第4期33-35,6,共3页Computer Applications Of Petroleum

摘　　要：介绍了二次筛选分解算法的基本设计思想,阐述了GF(2)上寻找稀疏矩阵的线性相关列的重要性。详细论述了有限域上寻找稀疏矩阵线性相关列的Lanczos方法和分块Lanczos算法,给出了分块Lanczos算法的具体描述,侧重分析了算法复杂度和算法实现的若干关键技术。对二次筛选法分解二进制数150位、172位和192位时所产生的大型稀疏矩阵B,利用Visual C++6 实现分块Lanczos算法,并进行了线性相关列的求解实验。This paper introduces the basic design idea of quadratic sieve large number factorization algorithm and importance of finding column dependencies in a sparse matrix over GF(2). Finding column dependencies in a sparse matrix over finite field using Lanczos algorithm and block Lanczos algorithm are described in detail. It analyses the complexity of the algorithm and some key technology of implementation. Implementing the algorithm using Visual C++6, and obtain experimental result for the large sparse matrix B generated by factoring 150-bits,172-bits, and 192-bits number using quadratic sieve.

关 键 词：分块 算法复杂度 实现方法 C++ 稀疏矩阵 算法实现 求解算法 二进制数 线性相关 筛选法 

分 类 号：TE832[石油与天然气工程—油气储运工程] TP391[自动化与计算机技术—计算机应用技术]