一种LU分解与迭代法的结构策略及算法实现

在矩阵求解算法，直接法或迭代法都能．有效地求解大规模稀疏或病态矩阵，因此提出一种LU分解与迭代法结合的策略，采用LU分解对矩阵进行预处理，以提高迭代法的收敛性，并采用一种判断策略使矩阵的LU分解结果可最限度地重复利用，些结合策略应用于两种共轭梯度（CG）法，得到CLUCG和CLUTCG两种算法。它们已应用于模拟和混合信号电路模拟器ZeniVDE中，大量实验结果表明此结合策略是很有效的，得到的两种算法具有较好的速度和较好的收敛性。     

基于GaBP算法的快速潮流计算方法

研究在潮流迭代求解过程中雅可比矩阵方程组的迭代求解方法及其收敛性。首先利用PQ分解法进行潮流迭代求解,并针对求解过程中雅可比矩阵对称且对角占优的特性,对雅可比矩阵方程组采用高斯置信传播算法(GaBP)进行求解,再结合Steffensen加速迭代法以提高GaBP算法的收敛性。对IEEE118、IEEE300节点标准系统和两个波兰互联大规模电力系统进行仿真计算后结果表明：随着系统规模的增长,使用Steffensen加速迭代法进行加速的GaBP算法相对于基于不完全LU的预处理广义极小残余方法(GMRES)具有更好的收敛性,为大规模电力系统潮流计算的快速求解提供了一种新思路。     

闭合B样条曲线控制点的快速求解算法及应用

为了提高求解闭合B样条曲线控制点的速度,提出了一种基于专用LU分解的求解算法。根据控制点方程组系数矩阵的特点,参照追赶法的LU分解,构造了分解后的、矩阵的结构。基于这两个矩阵的结构特征设计了专用的LU分解方法,具有较少的存储空间和计算量。在此基础上,根据追赶法的原理,设计了闭合B样条曲线控制点的快速求解算法。通过数值实验和在等值线光滑中的实际应用,表明了该算法的可靠性和有效性。     

利用弦长参数插值拟合光滑闭合B样条曲线构造方法

文章针对非均匀采样点拟合光滑B样条曲线构造问题,提出一种基于已知控制点和相邻控制点之间弦长求解控制点方程组系数矩阵来构造光滑B样条曲线的方法。该方法通过控制顶点所在曲线的光顺性提高最终生成曲线的连续性和光滑性。在此基础上,设计了闭合B样条曲线控制点的快速求解算法。首先利用所有控制顶点和相邻点间弦长建立求解系数的参数矩阵,再提出一种基于LU矩阵分解的优化算法。根据方程组系数矩阵的特点,参照追赶法的LU分解,构造了分解后的L、U矩阵结构。最后通过实例说明,采用文中方法所构造的B样条曲线具有较好的光滑性,也证明了该算法的可靠性和有效性。     

不同矩阵分解方法对海洋数据同化的影响*

在海洋数据同化领域,集合最优插值方法中,矩阵求逆过程所使用的奇异值分解(singular value decomposition,SVD)十分耗时。对集合最优插值中逆矩阵的求逆过程进行优化,分别使用LU分解、Choleskey分解、QR分解来替代SVD分解。首先,通过LU分解(Choleskey分解或QR分解)得到相应的三角矩阵(或正交矩阵);然后,利用分解后的矩阵来实现相关逆矩阵的计算。由于LU分解、Choleskey分解、QR分解的算法复杂度都远小于SVD分解,因此改进后的同化程序能得到大幅度的性能提升。数值结果表明,所采用的三种矩阵分解方法相比于SVD分解,都能将集合最优插值的计算效率提升至少两倍以上。值得一提的是,在四种矩阵分解中Choleskey分解使得整个同化程序的性能达到了最优。     

两种解线性方程组方法的C程序实现

线性方程组的数值解法一般有两类：直接法和迭代法。直接法中的平方根法．就是利用对称正定矩阵的三角分解而得到的求解对称正定方程组的一种有效方法。迭代法中的雅克比迭代法是一种比较常用的方法．它公式简单，每迭代一次只需计算一次矩阵和向量乘法。本文通过示例介绍了这两种解线性方程组的方法的C程序实现。     

两种解线性方程组方法的C程序实现

线性方程组的数值解法一般有两类:直接法和迭代法。直接法中的平方根法,就是利用对称正定矩阵的三角分解而得到的求解对称正定方程组的一种有效方法。迭代法中的雅克比迭代法是一种比较常用的方法,它公式简单,每迭代一次只需计算一次矩阵和向量乘法。本文通过示例介绍了这两种解线性方程组的方法的C程序实现。     

新预处理ILUCG法求解稀疏病态线性方程组

大型稀疏病态线性方程组的高效求解在科学计算和工程应用中起着十分重要的作用.对于一般非对称正定的非奇异线性代数方程组,首先介绍常用的不完全LU分解预处理矩阵构造技术;然后给出SSOR预处理分解及其改进分解,并基于ILUCG思想提出新预处理ILUCG法同时给出收敛性分析;最后进行数值模拟仿真试验,数值结果表明该算法是有效可行的,且较之一般的预处理ILUCG方法该法在求解稀疏病态方程组方面具有优越性.     

矩阵三角分解在数字水印中的应用

将非奇异矩阵进行三角分解是一种将复杂矩阵变换为简单矩阵的方法,也是分析矩阵特性的方法。而数字图像也可以看作矩阵,根据图像的这一特点结合小波变换提出一种鲁棒性较好的水印算法。首先对图像进行离散小波分解,分解的尺度由水印信息量大小决定;然后计算分解后最高尺度的细节矩阵的方差,选择方差最大的一个进行预处理,若其是奇异矩阵,通过一个置换矩阵将其转换为非奇异矩阵,这里置换矩阵可以当作密钥;然后对其进行LU分解,得到两个具有良好分布特性的三角矩阵;最后将置乱后的水印信息嵌入到两个矩阵的非零像素值中。实验结果证明该算法简单易行,具有较好的鲁棒性和安全性。     

大型稀疏线性方程组符号LU分解法

基于有限元总刚矩阵的大规模稀疏性、对称性等特性,采用全稀疏存储结构以及最小填入元算法,使得计算机的存储容量达到最少。为了节省计算机的运算时间,对总刚矩阵进行符号LU分解方法,大大减少了数值求解过程中的数据查询。这种全稀疏存储结构和符号LU分解相结合的求解方法,使大规模稀疏线性化方程组的求解效率大大提高。数值算例证明该算法在时间和存贮上都较为占优,可靠高效,能够应用于有限元线性方程组的求解。     

Parallel methods for optimality criteria-based topology optimization

Topology optimization problems require the repeated solution of finite element problems that are often extremely ill-conditioned due to highly heterogeneous material distributions. This makes the use of iterative linear solvers inefficient unless appropriate preconditioning is used. Even then, the solution time for topology optimization problems is typically very high. These problems are addressed by considering the use of non-overlapping domain decomposition-based parallel methods for the solution of topology optimization problems. The parallel algorithms presented here are based on the solid isotropic material with penalization (SIMP) formulation of the topology optimization problem and use the optimality criteria method for iterative optimization. We consider three parallel linear solvers to solve the equilibrium problem at each step of the iterative optimization procedure. These include two preconditioned conjugate gradient (PCG) methods: one using a diagonal preconditioner and one using an incomplete LU factorization preconditioner with a drop tolerance. A third substructuring solver that employs a hybrid of direct and iterative (PCG) techniques is also studied. This solver is found to be the most effective of the three solvers studied, both in terms of parallel efficiency and in terms of its ability to mitigate the effects of ill-conditioning. In addition to examining parallel linear solvers, we consider the parallelization of the iterative optimality criteria method. To tackle checkerboarding and mesh dependence, we propose a multi-pass filtering technique that limits the number of “ghost” elements that need to be exchanged across interprocessor boundaries.     

Explicit approximate inverse preconditioning techniques

Summary  The numerical treatment and the production of related software for solving large sparse linear systems of algebraic equations, derived mainly from the discretization of partial differential equation, by preconditioning techniques has attracted the attention of many researchers. In this paper we give an overview of explicit approximate inverse matrix techniques for computing explicitly various families of approximate inverses based on Choleski and LU—type approximate factorization procedures for solving sparse linear systems, which are derived from the finite difference, finite element and the domain decomposition discretization of elliptic and parabolic partial differential equations. Composite iterative schemes, using inner-outer schemes in conjunction with Picard and Newton method, based on approximate inverse matrix techniques for solving non-linear boundary value problems, are presented. Additionally, isomorphic iterative methods are introduced for the efficient solution of non-linear systems. Explicit preconditioned conjugate gradient—type schemes in conjunction with approximate inverse matrix techniques are presented for the efficient solution of linear and non-linear system of algebraic equations. Theoretical estimates on the rate of convergence and computational complexity of the explicit preconditioned conjugate gradient method are also presented. Applications of the proposed methods on characteristic linear and non-linear problems are discussed and numerical results are given.     

A class of iterative methods for finite element equations

A general method in the form of an accelerated preconditioned iterative refinement method (including some wellknown iterative methods and direct factorization methods) is presented for the solution of symmetric, sparse matrix problems. An analysis of one such approximate factorization, the SSOR method, is given, and some inherently advantageous properties of the conjugate gradient acceleration method are pointed out. A comparison is made of the computational complexity and storage in the SSOR preconditioned method with some direct methods applied to second order discretized boundary value problems. For plane problems of average size the direct methods are somewhat faster if enough right hand sides are present. For large enough problems (large number of nodes) the iterative method is faster. For three-dimensional problems no Cholesky factorization method can compete with the SSOR preconditioned method, not even for average sized problems.     

应用预处理AWE技术快速计算导体目标宽带RCS

应用渐近波形估计技术计算目标宽带雷达散射截面（RCS）,可有效提高计算效率。然而当目标为电大尺寸时,阻抗矩阵求逆运算将十分耗时,甚至无法计算。提出使用Krylov子空间迭代法取代矩阵逆来求解大型矩阵方程,应用双门槛不完全LU分解预处理技术降低迭代求解所需的迭代次数。数值计算表明,该方法结果与矩量法逐点求解结果吻合良好,并且计算效率大大提高。     

Parallel and Systolic Solution of Normalized Explicit Approximate Inverse Preconditioning

A new class of normalized approximate inverse matrix techniques, based on the concept of sparse normalized approximate factorization procedures are introduced for solving sparse linear systems derived from the finite difference discretization of partial differential equations. Normalized explicit preconditioned conjugate gradient type methods in conjunction with normalized approximate inverse matrix techniques are presented for the efficient solution of sparse linear systems. Theoretical results on the rate of convergence of the normalized explicit preconditioned conjugate gradient scheme and estimates of the required computational work are presented. Application of the new proposed methods on two dimensional initial/boundary value problems is discussed and numerical results are given. The parallel and systolic implementation of the dominant computational part is also investigated.     

Generalized newton multi-step iterative methods GMNp,m for solving system of nonlinear equations

A generalization of the Newton multi-step iterative method is presented, in the form of distinct families of methods depending on proper parameters. The proposed generalization of the Newton multi-step consists of two parts, namely the base method and the multi-step part. The multi-step part requires a single evaluation of function per step. During the multi-step phase, we have to solve systems of linear equations whose coefficient matrix is the Jacobian evaluated at the initial guess. The direct inversion of the Jacobian it is an expensive operation, and hence, for moderately large systems, the lower-upper triangular factorization (LU) is a reasonable choice. Once we have the LU factors of the Jacobian, starting from the base method, we only solve systems of lower and upper triangular matrices that are in fact computationally economical. The developed families involve unknown parameters, and we are interested in setting them with the goal of maximizing the convergence order of the global method. Few families are investigated in some detail. The validity and numerical accuracy of the solution of the system of nonlinear equations are presented via numerical simulations, also involving examples coming from standard approximations of ordinary differential and partial differential nonlinear equations. The obtained results show the efficiency of constructed iterative methods, under the assumption of smoothness of the nonlinear function.     

Penalized nonnegative matrix tri-factorization for co-clustering

Nonnegative matrix factorization has been widely used in co-clustering tasks which group data points and features simultaneously. In recent years, several proposed co-clustering algorithms have shown their superiorities over traditional one-side clustering, especially in text clustering and gene expression. Due to the NP-completeness of the co-clustering problems, most existing methods relaxed the orthogonality constraint as nonnegativity, which often deteriorates performance and robustness as a result. In this paper, penalized nonnegative matrix tri-factorization is proposed for co-clustering problems, where three penalty terms are introduced to guarantee the near orthogonality of the clustering indicator matrices. An iterative updating algorithm is proposed and its convergence is proved. Furthermore, the high-order nonnegative matrix tri-factorization technique is provided for symmetric co-clustering tasks and a corresponding algorithm with proved convergence is also developed. Finally, extensive experiments in six real-world datasets demonstrate that the proposed algorithms outperform the compared state-of-the-art co-clustering methods.     

Inherited LU factorization for solving fuzzy system of linear equations

In this paper, we use the inherited LU factorization for solving the fuzzy linear system of equations. Inherited LU factorization is a type of LU factorization which is very faster and simpler than the traditional LU factorization. In this case, we prove some theorems to introduce the conditions that the inherited LU factorization exists for the coefficient matrix of fuzzy linear system. The examples illustrate that the proposed method can be used in order to find the solution of a fuzzy linear system simply.     

Preconditioned variational methods on rotated finite difference discretisation

Due to their rapid convergence properties, recent focus on iterative methods in the solution of linear system has seen a flourish on the use of gradient techniques which are primarily based on global minimisation of the residual vectors. In this paper, we conduct an experimental study to investigate the performance of several preconditioned gradient or variational techniques to solve a system arising from the so-called rotated (skewed) finite difference discretisation in the solution of elliptic partial differential equations (PDEs). The preconditioned iterative methods consist of variational accelerators, namely the steepest descent and conjugate gradient methods, applied to a special matrix ‘splitting’ preconditioned system. Several numerical results are presented and discussed.     

最速下降与共轭梯度在数字波束形成中的研究

在自适应波束形成技术中,共轭梯度法是求解最优化问题的一种常用方法,最速下降法在不需要矩阵求逆的情况下,通过递推方式寻求加权矢量的最佳值。文中将最速下降法与共轭梯度法有机结合,构造出一种混合的优化算法。该方法在每次更新迭代过程中,采用负梯度下降搜索方向,最优自适应步长,既提高了共轭梯度算法的收敛速度,又解决了最速下降法在随相关矩阵特征值分散程度增加而下降缓慢的问题,具有收敛速度快,运算量低的特点。计算机仿真给出了五阵元均匀线阵的数字波束形成系统实例,分别从波束形成、误差收敛及最佳权值等方面与传统LMS 算法进行了比较分析,结果表明了该方法的可行性与有效性。