解一种稀疏线方程组的快速算法

A Fast Algorithm for Solving a Kind of Spare Systems of Linear Equaticns

设AX=b是-m×n线方程组,其中每个方程最多仅含两个未知数(以下简称方程组(Ⅰ),本文给出解此类方程组的一个快速算法。算法分两步,第一步用行,列置换使系数矩阵A变换为某种标准形式PAQ(P、Q为置换阵);第二步由由PAQ构造一有向图,进而对此图的顶点进行标定而解出方程。第一步的时间复杂性为0(n^(0.5)m),第二步在最坏的情况下要求7m-5次算术运算。

In this Paper we present a fast algorithm for Solving m×n Systems of Lin-ear equations Ax - b With at most two Variables Per eguation.The algorithmrelies upon the Graph Theory, first we Construct a directed Graph and theSystems of Linear equatians then will be Solved by Labeling the Vertices of thegraph.