Cholesky分解递归算法与改进

递归算法是计算稠密线性代数的一种新的有效方法。递归产生自动、变化的矩阵分块,能充分发挥当今分级存储高性能计算机的效率。对Cholesky分解递归算法进行了研究,给出了算法的详细推导过程,用具有递归功能的Fortran90实现了算法,并通过矩阵元素顺序重排的方法,进一步提高了递归算法的运算速度。研究产生的算法比目前常用的分块算法快15％－25％。     

基于LDLT分解求实对称矩阵特征值的递归算法

基于线性代数与矩阵理论,给出利用LDLT分解计算实对称矩阵特征值的递归算法。该算法可求出实对称矩阵在给定区间内的特征值的个数,并可计算满足精度要求的特征值。理论分析和实际测试证明该算法是有效的。     

递归算法的非递归化实现

由递归算法直接转换成相应的非递归算法能有效地提高程序的执行效率，本文列出了几类递归算法的非递归化实现方法，分别说明了这几类递归算法的特点及算法实例，并给出了相应的非递归算法。     

矩阵的Doolittle递归分解算法及符号程序设计

将矩阵An×n的Doolittle分解推广到Am×n上，并在常规的迭代算法上加以创新，给出了递归的分解算法．在实现算法的过程中，对数据进行了巧妙处理，使中间数据及最终计算结果都具有分数形式，提高了结果的精确度，而且更符合人们阅读的习惯．经过运行测试，算法设计合理，程序运行高效准确．程序是对MathSoft公司的交互式的数学文字软件Mathcad的矩阵分解的数值计算扩充到符号运算．     

分治递归算法的解题能力

为了培养学习编程的逆向思维，运用分治思想的递归算法提高解决问题的能力，理解分治和递归的关系，掌握递归算法解决问题的条件和原理是十分必要的。从提出问题、分析问题、抽象问题的特征、解决问题和分析递归算法的局限性的过程，运用比较法比较迭代与递归之间的关系，结合具体问题，对理解递归算法解决问题给出了有效的方法。用分治的递归方法求解问题，其结构简单，可读性强，但是递归算法理解起来有一定难度，研究了递归算法的特征、递归与分治之间的关系、递归与迭代之间的关系，根据时间和空间复杂度，给出了递归算法的深度建议。实践的结果证明，采用这样的方式，能够帮助读者理解逆向思维和分治思想的本质，提升运用递归算法解决生活和学习中的问题的能力。     

Smith图导出关系模式的分解算法与递归处理

本文提出了一种由优化的Ｓｍｉｔｈ图导出规范化关系模式的分解算法,包括确定根结点、,生成森林、导出规范化、关系模式等。这些都是用递归处理实现的,本文给出了这些递归处理的描述,最后介绍了一个例子。     

递归的非递归算法研究

本文对递归的非递归算法进行了研究，并给出了由递归到递推的抽象算法，并说明了该算法的具体运用。     

按自动选择正交面递归分解三视图的三维重建*

针对随着构成三视图环路数的增加,三维重建的计算时间和难度将成倍增加的问题,提出了一种通过自动选择正交面递归分解三视图的三维重建算法和实例。该算法能在构成三视图的各种图线组合中,自动选择出能简化三维重建难度的正交分解面,并用其不断地对三视图进行递归分解。该分解算法的使用将会扩大三维重建的范围和降低三维重建的时间和难度。     

下期要目

虽然二叉树遍历的递归算法易于编写和理解，但递归算法有其自身无法克服的固有缺点，即与功能等价的非递归算法相比，既花费更多的机器时间，又耗用更多的内存，与程序性能直接矛盾。当应用场合追求程序性能时(如在实时系统中)，递归算法就难以满足要求，这时唯有非递归算法，才能派上用场。因此，非递归算法设计理所当然地成为程序设计领域的一     

论递归算法的非递归化

递归算法简单自然、结构清晰、易写易读、易于验证其正确性，但执行效率不高。因此，在程序设计中，通常对所要处理的问题先用递归算法加以描述，然后再将其改写成非递归算法。本文从四个方面论述了递归算法的模拟问题。     

LU分解递归算法的实现

§1.引言 以LU分解, Cholesky分解等为代表的线性代数问题的数值计算在现代科学研究和工程技术中得到广泛应用.随着计算机技术的发展,实现这些线性代数数值计算的计算机算法和软件也在不断发展.目前,具有多级存储结构的高性能RISC计算机已占据了数值计算领域的主导地位. RSIC处理器的运算速度非常快,它们与存储器之间的速度差距很大.计算机的性能能不能充分发挥,多级存储结构与高缓能否得到有效利用成为关键.为此,现行的     

A new computationally efficient fixed-interval,discrete-time smoother

The Rauch-Tung-Streibel smoother recursion is used to derive a new smoother algorithm based upon a decomposition of the linear model dynamical equation and maximizing use of rank 1 matrix modification. This new algorithm, it turns out, parallels Bierman's forward recursive square-root information filter/backward recursive U-D factorized covariance algorithm. The new result features computational efficiency, reliance on numerically stable matrix modification algorithms, and reduced computer storage.     

乔莱斯基分解递归算法的研究

1 引言以乔莱斯基(Cholesky)分解、LU分解等为代表的线性代数问题的数值计算在现代科学研究和工程技术中得到广泛应用。随着计算机结构和技术的发展,实现这些线性代数数值计算的计算机算法和软件也在不断发展。通用的基本线性代数子程序库BLAS(Basic Lin-ear Algebra Subprograms)从70年代的Level-1 BLAS(执行向量一向量运算),发展到80年代的Level-2     

Recursion based parallelization of exact dense linear algebra routines for Gaussian elimination

We present block algorithms and their implementation for the parallelization of sub-cubic Gaussian elimination on shared memory architectures. Contrarily to the classical cubic algorithms in parallel numerical linear algebra, we focus here on recursive algorithms and coarse grain parallelization. Indeed, sub-cubic matrix arithmetic can only be achieved through recursive algorithms making coarse grain block algorithms perform more efficiently than fine grain ones. This work is motivated by the design and implementation of dense linear algebra over a finite field, where fast matrix multiplication is used extensively and where costly modular reductions also advocate for coarse grain block decomposition. We incrementally build efficient kernels, for matrix multiplication first, then triangular system solving, on top of which a recursive PLUQ decomposition algorithm is built. We study the parallelization of these kernels using several algorithmic variants: either iterative or recursive and using different splitting strategies. Experiments show that recursive adaptive methods for matrix multiplication, hybrid recursive–iterative methods for triangular system solve and tile recursive versions of the PLUQ decomposition, together with various data mapping policies, provide the best performance on a 32 cores NUMA architecture. Overall, we show that the overhead of modular reductions is more than compensated by the fast linear algebra algorithms and that exact dense linear algebra matches the performance of full rank reference numerical software even in the presence of rank deficiencies.     

On smoothing in linear discrete systems with time delays†

An algorithm is presented for optimal linear fixed-point and fixed-lag smoothing in non-stationary linear discrete systems with multiple time delays. Relations derived previously in the problem of filtering are used directly to obtain the fixed-point and fixed-lag smoothing filters. The smoothing error covariance matrix is obtained via a recursive matrix equation. For the particular case of systems without delay terms, the algorithm defines new smoothing procedures.     

Optimal linear regulator pole-placement by weight selection

A recursive algorithm for selecting the state weighting matrix of a linear quadratic regulator (LQR) problem to result in a set of desired closed-loop eigenvalues is presented. Aggregation is used so that at each step of the recursive process where either a real pole or a complex conjugate pair is being placed, one has to deal with two or four dimensional matrix equations regardless of the system's dimensionality. In addition the algorithm is capable of placing a complex conjugate pair at a new complex conjugate location, or at two distinct real locations.     

On-line estimation of the parameters of a multivariable system using matrix pseudo-inverse

A recursive pseudo-inverse algorithm is presented for estimating the parameters of the transfer-function matrix of a multiple-input-multiple-output discrete-time system from the samples of the input-output data. The algorithm is suitable for on-line identification of linear multivariable systems.     

基于递归耦合方法的三对角线性方程组分布式并行算法

提出了一种在分布式计算机上用递归倍增方法解三对角线性方程组的并行算法。通过研究算法中的额外开销达到优化标量算法的执行和通讯,并减少了存储开销。当三对角线性方程组的系数矩阵满足对角占优时,该算法在运行过程中不会中断。最后,在采用消息传递编程模型的基于局域网MPI并行环境下对算法进行了评价。数值实验结果表明,该算法是高效的。     

Linear estimation in Krein spaces. I. Theory

The authors develop a self-contained theory for linear estimation in Krein spaces. The derivation is based on simple concepts such as projections and matrix factorizations and leads to an interesting connection between Krein space projection and the recursive computation of the stationary points of certain second-order (or quadratic) forms. The authors use the innovations process to obtain a general recursive linear estimation algorithm. When specialized to a state-space structure, the algorithm yields a Krein space generalization of the celebrated Kalman filter with applications in several areas such as H ^∞-filtering and control, game problems, risk sensitive control, and adaptive filtering