一类块三对角矩阵的计算

通过构造一个矩阵序列,给出了一类块三对角线性方程组的解耦算法,并用来求解其线性方程组.进而将其思想方法应用于块三对角矩阵行列式的计算.与现有的算法比较,此算法具有计算量和存贮量较少,且编程较简单的特点.     

求解分块循环三对角方程组的新算法

分块循环三对角方程组的求解在科学与工程计算中有着广泛的应用.本文根据分块循环三对角矩阵的特殊分解,给出了求解分块循环三对角方程组的一种新算法.该算法含有可以选择的参数矩阵,适当选择这些参数矩阵,可以使得计算精度高于追赶法,甚至当追赶法失效时,由该算法仍可得到一定精度的解.而数值算例的结果与理论分析的结果也吻合.     

块三对角线性方程组的一种分布式并行算法

提出了分布环境下求解三对角线性方程组的一种并行算法,该算法基于对计算量的仔细估算,合理地将方程组求解工作分配到各处理机,达到负载平衡,同时,充分地将计算与通信重叠,减少处理机空闲时间;当块三以角线性方程组的系数矩阵为对角占优时,算法在执行过程中不会中断;文中分析了算法的复杂性,给出了在分析布存储多计算机系统上的数值试验结果,数值结果表明,文中算法的效率较Ｃｈｕｎｇ等的算法有较大的提高。     

解三对角方程组的分段约化法

本文利用矩阵的三角分解,给出了求解三对角方程组的一个新的并行算法。该算法利用了分段法及循环约化法的特点,具有计算量少,并行性好,程序实现方便等优点,该算法还可推广运用于带状线性方程组,对于高阶方程组尤为有效。     

循环三对角线性方程组的一种分布式并行算法

１．引 言 循环三对角线性方程组的求解是诸多应用问题的重要组成部分．例如,周期的样条插值就导致对角占优的循环三对角线性方程组的求解［１］,当边界条件为周期边界条件时,一些偏微分方程的离散化也可能导致循环三对角线性方程组的求解．适应计算机体系结构发展的此类方程组的算法研究,是数值并行算法的重要问题之一．文献［２］讨论了适用于共享主存并行机的此类方程组的并行算法,在 Ｍｌｌｅｒ和 Ｓｃｈｅｅｒｅｒ［３］提出的并行化Ｈ对角线性方程组解法的划分方法基础上,Ｃｈｕｎｇ［４］等对循环块三对角线性方程组进行了研究…     

块三对角线性方程组的一种并行迭代算法

系统工程计算在科学计算中,单台处理机不能满足需要,为提高计算效率和精度,采用并行处理是一个非常好的块三对角线性方程组的办法,提出了分布式环境下求解块三对角线性方程组的一种并行计算,算法是充分利用系数矩阵结构的特殊性,通过对系数矩阵进行适当地分解构造的迭代算法,使得算法需要在相邻处理机之间进行并行通信三次.并从理论上给出了算法收敛的一个充分条件.最后,在HP rx2600集群上进行了数值仿真,结果表明,实算与理论是一致的,提高了并行效率和精度.     

无限制背包问题的爬山算法

给出了一种求解整数背包问题的爬山解法 ,并对该算法的计算复杂度及最坏情形进行了理论分析 .通过与经典的求解背包问题方法的对比研究 ,给出了该算法的适用范围并展示其优越性 .数值实验表明 ,该算法简便易行 ,在其适用范围内具有计算复杂度低 ,近优程度高等优点 .     

关于三对角线性方程组的高效并行计算

求解三对角线性方程组已有很多并行算法。我们知道,倍增法需18log_2N步,奇偶消去法需12log_2N步,循环奇偶约化法需10log_2N步。文[5]给出一种仅需5logN步的并行算法,但算法较复杂,而且在稳定性方面有一定的局限性。本文重新分析了奇偶消去法的计算复杂性。结果表明,其并行步数可达4log_2N步,而所需处理机台数不超过6N台。从而,奇偶消去法不失为一种稳定有效的并行算法。特别地,对T型三对角方程组,提供了一个复杂性与[3]相当的新算法。     

基于差分方程计算循环复杂度符号化上界

计算程序中循环的程序复杂度符号化上界可以验证程序的停机性.基于差分方程和最优化问题求解技术,给出了一种计算P*-solvable循环程序复杂度符号化上界的有效方法.分别针对含有赋值语句的循环和带条件分支的循环,提出了其程序复杂度符号化上界计算方法.与其他工作相比,该方法能够计算得到更精确的循环复杂度符号化上界,实验结果...     

用参数法求一些特殊的线性代数方程组的数值解

本文将求解线性方程组数值解的双参数法进行推广,得到(?)种求解一些特殊的线性方程组的较为(?)般的方法-参数法,并具体给出利用三组参数求解拟二对角方程组和拟Hessen-berg方程组的算法.此算法具有明显的优越性.比如,在求解拟二对角方程组时,和利用LU分解法相比,乘除运算的次数由11n-16变为9n+20,所需要设定的向量组由5个降为4个.在求解拟Hessenberg方程组时,和Gauss消去法相比,除法运算的次数由1/2n(n+1)变为3n-4.这对求解大型的拟三对角方程组和拟Hessenberg方程组非常有利.当然,此种方法还可以用来求解其它一些方程组。     

A Parallel Solver for Circulant Toeplitz Tridiagonal Systems on Hypercubes

Solving circulant Toeplitz tridiagonal systems arises in many engineering applications. This paper presents a fast parallel algorithm for solving this type of systems. The number of floating-point operations required in our algorithm is less than the previous parallel algorithm [cf. Kim and Lee (1990)] for solving the similar system. Specifically, an overlapping technique is proposed to reduce the communication steps required. In addition, an error analysis is given. The implementation of our algorithm on the nCUBE2/E with 16 processors has been carried out. The experimental results show that the speedup is almost linearly proportional to the number of processors.     

A multilevel parallel solver for block tridiagonal and banded linear systems

This paper describes an efficient algorithm for the parallel solution of systems of linear equations with a block tridiagonal coefficient matrix. The algorithm comprises a multilevel LU-factorization based on block cyclic reduction and a corresponding solution algorithm.

The paper includes a general presentation of the parallel multilevel LU-factorization and solution algorithms, but the main emphasis is on implementation principles for a message passing computer with hypercube topology. Problem partitioning, processor allocation and communication requirement are discussed for the general block tridiagonal algorithm.

Band matrices can be cast into block tridiagonal form, and this special but important problem is dealt with in detail. It is demonstrated how the efficiency of the general block tridiagonal multilevel algorithm can be improved by introducing the equivalent of two-way Gaussian elimination for the first and the last partitioning and by carefully balancing the load of the processors. The presentation of the multilevel band solver is accompanied by detailed complexity analyses.

The properties of the parallel band solver were evaluated by implementing the algorithm on an Intel iPSC hypercube parallel computer and solving a larger number of banded linear equations using 2 to 32 processors. The results of the evaluation include speed-up over a sequential processor, and the measure values are in good agreement with the theoretical values resulting from complexity analysis. It is found that the maximum asymptotic speed-up of the multilevel LU-factorization using p processors and load balancing is approximated well by the expression (p +6)/4.

Finally, the multilevel parallel solver is compared with solvers based on row and column interleaved organization.     

Complexity bounds for solving some tridiagonal systems with preconditioning

Some special classes of tridiagonal matrices A are considered, and the complexity of solving a linear system Ax=f is investigated, when rational preconditioning on A is allowed. Non-trivial lower bounds are found, and in all cases the number of necessary multiplicative operations, apart from preconditioning, is shown to be greater than the number of indeterminates defining A.     

A fast algorithm for solving special tridiagonal systems

In this paper, a fast algorithm for solving the special tridiagonal system is presented. This special tridiagonal system is a symmetric diagonally dominant and Toeplitz system of linear equations. The error analysis is also given. Our algorithm is quite competitive with the Gaussian elimination, cyclic reduction, specialLU factorization, reversed triangular factorization, and Toeplitz factorization methods. In addition, our result can be applied to solve the near-Toeplitz tridiagonal system. Some examples demonstrate the good efficiency and stability of our algorithm.     

Limiti per il numero di condizione di una classe di matrici tridiagonali e tridiagonali a blocchi

Bounds of the condition number for a large classes of tridiagonal and block tridiagonal matrices are obtained. Since they use only information taken from the elements of the original matrix, without computing the inverse explicitly, their cost reduces to few arithmetic operations.

---

---

Lavoro svolto nell'ambito delle attività del “Centro Interuniversitario di Matematica Computazionale” con il contributo del Ministero della Pubblica Istruzione. Classificazione AMS 65F05.     

A split-correct parallel algorithm for solving tridiagonal symmetric toeplitz systems

In 1994, Yan and Chung produced a fast algorithm for solving a diagonally dominant symmetric Toeplitz tridiagonal system of linear equations Ax = b. In this work a method will be presented which will allow for problems of the above nature to be split into two separate systems which can be solved in parallel, and then combined and corrected to obtain a solution to the original system. An error analysis will be provided along with example cases and time comparison results.     

三对角线性方程组的一种有效分布式并行算法

提出了分布式存储环境下求解三对角线性方程的一种并行算法,该算法基于“分而治之”的策略,高效地形成并求解其缩减方程组,避免不必要的冗余计算,通过对计算量的仔细估计,较好地平衡了各处理机的负载;同时,充分利用了计算与通信重叠技术,减少处理机空闲时间,分析了自救的复杂性,给 分布存储多计算机系统上的数值试验结果,数值结果表明,算法的效率较迟利华和李晓梅的ＤＰＰ算法有较大的提高。     

Hermitian tridiagonal solution with the least norm to quaternionic least squares problem

Quaternionic least squares (QLS) is an efficient method for solving approximate problems in quaternionic quantum theory. In view of the extensive applications of Hermitian tridiagonal matrices in physics, in this paper we list some properties of basis matrices and subvectors related to tridiagonal matrices, and give an iterative algorithm for finding Hermitian tridiagonal solution with the least norm to the quaternionic least squares problem by making the best use of structure of real representation matrices, we also propose a preconditioning strategy for the Algorithm LSQR-Q in Wang, Wei and Feng (2008) [14] and our algorithm. Numerical experiments are provided to verify the effectiveness of our method.