追赶法并行求解循环三对角方程组

给出了求解循环三对角线性方程组的一种并行算法.在系数矩阵满足对角占优的条件下,利用该方法能够快速、稳定地求解循环三对角线性方程组,在单个进程上的计算量仅为○(17n).与传统算法求解循环三对角线性方程组的计算量相同.而且,本算法可以方便地实施分布式并行计算,各进程仅需向主进程传递8个实数,而主进程向各子进程传递2个实数,通讯量较小.数值实验结果表明:对于大规模的循环三对角线性方程组.利用16个进程计算的并行效率均在0_75以上.求解三对角线性方程组的传统追赶法实则是本文算法的一种特例,因此.该算法也可用于求解三对角线性方程组.     

求解循环三对角方程组的追赶法

利用LU分解的思想,首先将循环三对角方程组的系数矩阵A分解成3个矩阵的乘积LUD,其中L是下三角矩阵,U是单位上三角矩阵,D是拟对角矩阵(每行只有两个非零元素,前n-1行非零元位于主对角线和最后一列上,第n行非零位于第1列和最后一列上);然后,运用追赶法的思想依次用前代法("追")解出Lu=d的解,回代法("赶")解出Uv=u的解;再利用Dx=v的第一行和最后一行求出未知量Xn,进而回代求解出所有未知量.该方法虽然将系数矩阵分解成3个矩阵的乘积,但计算过程并不复杂,总的算数运算量只有O(14n).小于传统算法的计算量(O(17n)).文章对数值计算的稳定性进行了分析.当矩阵A对角占优且2|ai|≤|bi|时,算法是数值稳定的.数值试验结果与理论分析相吻合.     

追赶法求解拟五对角线性方程组

 根据拟五对角矩阵的特点,沿用追赶法的思想,首先将拟五对角系数矩阵分解成3个简单矩阵的乘积A=LUD,其中L为下三角形矩阵,U为单位上三角形矩阵,D为拟对角矩阵。然后将拟五对角线性方程组的求解问题转化为求解以下3个简单的线性方程组：Lz=f,Uy=z,Dx=y。通常的LU分解仅求解2个方程,本算法虽然将问题转化为3个方程组的求解,复杂度却没有增加,总的运算量仅为O（39n）。由于算法沿用追赶法矩阵分解的思想,对于严格对角占优的五对角线性方程组具有良好的数值稳定性。数值结果表明,算法的计算时间与方程组阶数n呈线性关系。     

求解拟五对角线性方程组的四参数法

 基于五对角线性方程组的追赶法,给出了拟五对角线性方程组的四参数求解方法。算法的基本思想是,将方程组的前2个未知量x1,x2和最后2个未知量xn－1,xn看作参数,这4个未知量正好对应于拟五对角方程组边角位置上的非零元素。然后通过特殊的矩阵分解将方程组解向量中的其他n－4个未知量用x1,x2,xn－1和xn 4个参数表示,从而形成标准的五对角线性方程组,可以方便地利用求解标准五对角线性方程组的追赶法进行求解。被看作参数的4个未知量可以利用原方程组中的前后两个方程及中间变量求出。最后,将已经求出的4个参数再代入分解矩阵形成的方程组中求得其余分量。鉴此,本文给出了两种不同的实现方法,其主要区别在于求解4个参数的过程不同。一种方法是将解向量的全部分量用参数线性表出,然后取出前后各2个式子组成参数方程,求出4个参数。另一种方法是将4个参数作为已知量先代入第3～n－2个方程中,整理后得到一个n－4阶的方程组,解出第3～n－2个解分量的参数表达式,再将x3,x4,xn－3,xn－2回代到前2个方程和最后2个方程中组成参数方程,求出4个参数。对于规模较大的拟五对角线性方程组而言,这两种算法的计算量几乎一样。该算法的数值稳定性分析结果表明,系数矩阵在满足严格对角占优的条件下,该算法是稳定的。数值实验结果表明,两种算法的实际计算时间与算法的理论分析相符合。     

求解拟五对角线性方程组的两参数法

针对拟五对角线性方程组的特点,选择最后两个未知量Xn-1和Xn作为参数(两参数法),将它们代入其他n-2个方程中,从而将原方程组的求解问题转化为求解3个五对角线性方程组.然后再求出参数Xn-1和Xn,最终求出全部解向量.由于算法的主要运算是运用追赶法求解五对角线性方程组,具有较好的数值稳定性.数据实验表明,与四参数算法...     

求解三对角方程组的并行追赶算法

通过分析影响算法的并行效率的主要因素,根据分而治之策略中的分块思想提出了一种求解三对角方程组的并行追赶算法。然后在机群系统中,MPI环境下实现了该并行算法,对并行算法的加速比和效率与原串行算法进行了比较,结果表明此算法有较高的计算效率。     

求解三对角方程组的并行追赶算法

通过分析影响算法的并行效率的主要因素,根据分而治之策略中的分块思想提出了一种求解三对角方程组的并行追赶算法。然后在机群系统中,MPI环境下实现了该并行算法,对并行算法的加速比和效率与原串行算法进行了比较,结果表明此算法有较高的计算效率。     

解两类特殊三对角线性方程组的修正追赶法

本文给出解两类特殊的三对角线性方程组的一种新方法,这类线性方程组常在数值解微分方程时出现。本算法的基础是求矩阵逆的著名的秩—修正法,数值例子表明该算法是有效的。     

求解一类周期三对角方程组的参数法

本文建立求解一类周期三对角和周期块三对角方程组数值解的参数算法.其运算量与求解线性方程组的LU分解法相比有明显的优势.数值实验表明此算法是有效的.     

并行求解拟三对角方程组的二分算法

用并行算法设计的基本技术－二分法，给出了拟三对角线性方程组的直接解法。     

循环三对角Toeplitz线性方程组的分组降阶算法

 运用并行算法中分而治之的思想,给出了一种求解循环三对角Toeplitz线性方程组的分组降阶串行算法。与求解同类问题的传统算法相比,分组降阶算法的优点在于它不仅大幅度减少了内存占用量,而且还大幅度减少了算术运算量。分组降阶算法可以通过3个步骤来实现。第一步是分组降阶,其基本思路是将一个n=μm阶的方程组按行分成μ组,每组m个方程;n维解向量也对应地分成μ组。第二步是构造参数方程组,也就是依据三对角系数矩阵的特点,给出各组解之间的关系式,把不属于该组的解分量看作参数。第三步是求解参数方程组和原方程组,在这一步中,首先求解参数方程组,然后再代入相应分组的关系式便可求出所有的解分量。对于三对角Toeplitz线性方程组,同样能减少内存占用量,从而在计算机性能不变的情况下,提高求解问题的规模,但与求解三对角Toeplitz线性方程组的传统算法相比运算量有所增加。数值实验结果表明,对于特定规模的方程组来说,总存在一个最佳的分组个数使得计算时间最少;随着方程组阶数的提高,最佳分组的个数也增大。     

三对角方程组贪心方法并行迭代法

利用正交投影方法、贪心方法和分治策略给出一种求解任意三对角方程组的新的并行迭代解法.证明了该解法对任意的相容性三对角方程组收敛.分析了解法的复杂性、数值稳定性和相容性.探讨了解法对应的消息传递MIMD并行算法的设计方法.     

解一类不定线性方程组的分块QR方法

本文应用矩阵分块技巧结合QR分解方法讨论了不定线方程组的解存在唯一的充分必要条件,并提出一种计算量较小的计算方法     

求解带扰动的线性方程组的贪婪随机Kaczmarz方法

当相容的线性代数方程组的右端向量发生扰动时,给出了由贪婪随机Kaczmarz方法所产生的迭代解与原线性代数方程组的最小范数解之间的期望误差的上界,并说明了随着迭代步数的增长,该期望解误差以线性速率下降至一个给定阈值。数值实验表明,该阈值能够很好地估计贪婪随机Kaczmarz方法的迭代解误差所能达到的最小值。     

三对角线性方程组的一种并行解耦算法

就三对角线性方程的求解，提出了一个适用于MIMD并行计算机的并行解耦算法，新的算法适用于工作站群式的分布式并行计算机(COW)，数值测试结果表明，当方程组的规模较大时，并行效率明显。     

三对角线性方程组行处理法

给出三对角线性方程组的行处理法迭代解法，探讨其收敛性与加速技术     

求解约束线性方程组的斜投影法

利用广义逆Ａｒ，ｓ的性质给出了求解约束线性方程组的斜投影法，并导出了与ＡＢＳ算法类似的递推计算格式。     

求解线性方程组的初参数方法

本文提出一种求解线性方程组的直接解法，该方法把较大方程组的求解化为可并行的较小方程组求解。可适用于大系统问题或高维数值解问题的求解，也可处理混合问题的不同区域，方法的实施与方程组的可解性无关。这对于求解变系数不定常问题是有意义的。