Symmetric-triangular decomposition and its applications part II: Preconditioners for indefinite systems

As an application of the symmetric-triangular (ST) decomposition given by Golub and Yuan (2001) and Strang (2003), three block ST preconditioners are discussed here for saddle point problems. All three preconditioners transform saddle point problems into a symmetric and positive definite system. The condition number of the three symmetric and positive definite systems are estimated. Therefore, numerical methods for symmetric and positive definite systems can be applied to solve saddle point problems indirectly. A numerical example for the symmetric indefinite system from the finite element approximation to the Stokes equation is given. Finally, some comments are given as well. AMS subject classification (2000) 65F10     

广义鞍点问题的块三角预条件子

本文对Golub和Yuan(2002)中给出的ST分解推广到广义鞍点问题上,给出了三种块预条件子,并重点分析了其中两种预条件子应用到广义鞍点问题上所得到的对称正定阵,得出了其一般的性质并重点研究了预处理矩阵条件数的上界,最后给出了数值算例.     

关于线性系统解的对称性算法的强稳定性的探索

关于线性方程解的算法方面,本文在对称非奇异矩阵类和对称正定矩阵类上给出了强稳定性算法.     

On symmetric block triangular splitting iteration method for a class of complex symmetric system of linear equations

For solving a class of complex symmetric linear system, we first transform the system into a block two-by-two real formulation and construct a symmetric block triangular splitting (SBTS) iteration method based on two splittings. Then, eigenvalues of iterative matrix are calculated, convergence conditions with relaxation parameter are derived, and two optimal parameters are obtained. Besides, we present the optimal convergence factor and test two numerical examples to confirm theoretical results and to verify the high performances of SBTS iteration method compared with two classical methods.     

子空间上的对称正定及对称半正定阵的左右特征值反问题

文[1][2][3]中讨论AX＝B的对称阵逆特征值问题，文[4][5][6]中讨论了半正定阵的逆特征值问题。本文讨论了空间了子空间上的对称正定及对称半正定阵的左右特征值反问题，给出了解存在的充分条件及解的表达式。     

含剩余对称平均的不等式及其应用

定义 n个正实数 x1,x2 ,… ,xn的剩余对称平均 ∑k ( x) ,借助于数学归纳法及优超理论证明当 x∈Rn+ + 时有 :∑2 ( x)≥ ∑3( x)≥…≥ ∑n ( x)≥ A( x) .并将此结果用于正定矩阵 ,n维长方体及单形 .     

三元对称形式的Schur分拆与不等式的可读证明

本文给出了一类三元对称形式(即对称齐次多项式)的一种分拆法,即将此类多项式表示成一类特定形式的正半定对称形式的线性组合,介绍分拆算法．并由此而给出了三元对称形式半正定的一个充分条件．     

一类增算子不动点定理及其应用

利用锥理论和非对称迭代方法,讨论了不具有连续性和紧性条件的增算子方程解的存在唯一性.作为其应用着重讨论了非增算子方程解的存在唯一性,并给出了迭代序列收敛于解的误差估计,改进和推广了某些已知结果.     

矩阵秩分解定理的一个证明及其应用

矩阵的秩分解定理是矩阵论中的一个基础性定理.本文给出了秩分解定理的一个证明,描述了其中可逆矩阵P,Q的构造,讨论了秩分解定理及其P,Q的构造在解线性方程组中的应用,以及在判别Sylvester不等式等号成立中的应用.     

一个矩阵分解算法的推广及应用

对样本相关系数矩阵等行和分解算法作了简化和推广,使算法不仅可以应用在基于正态总体非独立样本的假设检验问题,也可以有效地运用在最优化算法中牛顿法等与二次函数极小化有关的问题上.     

二次李三系的分解定理

有限维李三系称为二次的,如果它容许一个非退化的不变对称双线性型.无论是李三系分解为不可分解理想的直和,还是二次李三系分解为不可分解非退化理想的正交直和,证明了这两类分解在同构意义下都是唯一的.     

区域上Besov空间的原子分解和限制定理

本文在区域Ω（Ω 　 Ｒｎ，ｎ≥１）上定义了某类在边界上消失的Ｂｅｓｏｖ空 间Ｂ~（ｓ，ｑ）_（ｐ，ｏ）（Ω）（ｓ∈Ｒ，０＜ｐ，ｑ≤∞），并给出了它的原子分解，然后证明了当区域Ω∈ Ｄε（ｎ）（０＜ε≤１，ｐｓ＜ε）时，得到了限制定理Ｂ~（ｓ，ｑ）_（ｐ，ｏ）（Ω）＝Ｂ~（ｓ，ｑ）_（ｐ）（Ω）．     

特殊五对角与七对角对称正定矩阵的一类反问题

针对线性代数方程组Ax=b,利用矩阵分解的思想,构造一类特殊五对角与七对角对称正定阵的矩阵分解,获得这类矩阵反问题解存在的充要条件和通解表达式.最后,给出了具体算法与数值算例.     

Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition

We present efficient (parallel) algorithms for two hierarchical clustering heuristics. We point out that these heuristics can also be applied to solving some algorithmic problems in graphs, including split decomposition. We show that efficient parallel split decomposition induces an efficient parallel parity graph recognition algorithm. This is a consequence of the result of S. Cicerone and D. Di Stefano [[7]] that parity graphs are exactly those graphs that can be split decomposed into cliques and bipartite graphs.     

A REGULARIZED CONJUGATE GRADIENT METHOD FOR SYMMETRIC POSITIVE DEFINITE SYSTEM OF LINEAR EQUATIONS

AbstractA class of regularized conjugate gradient methods is presented for solving the large sparse system of linear equations of which the coefficient matrix is an ill-conditioned symmetric positive definite matrix. The convergence properties of these methods are discussed in depth, and the best possible choices of the parameters involved in the new methods are investigated in detail. Numerical computations show that the new methods are more efficient and robust than both classical relaxation methods and classical conjugate direction methods.     

Efficient and Optimal Parallel Algorithms for Cholesky Decomposition

In this paper, we consider the problem of developing efficient and optimal parallel algorithms for Cholesky decomposition. We design our algorithms based on different data layouts and methods. We thereotically analyze the run-time of each algorithm. In order to determine the optimality of the algorithms designed, we derive theoretical lower bounds on running time based on initial data layout and compare them against the algorithmic run-times. To address portability, we design our algorithms and perform complexity analysis on the LogP model. Lastly, we implement our algorithms and analyze performance data. This revised version was published online in July 2006 with corrections to the Cover Date.     

Ergodic Theorems and Ergodic Decomposition for Markov Chains

This paper considers Markov chains on a locally compact separable metricspace, which have an invariant probability measure but with no otherassumption on the transition kernel. Within this context, the limit providedby several ergodic theorems is explicitly identified in terms of the limitof the expected occupation measures. We also extend Yosidasergodic decomposition for Feller-like kernels to arbitrarykernels, and present ergodic results for empirical occupation measures, aswell as for additive-noise systems.     

对称不定系统的一类预处理子的注记

由于对称正定系统已有很多有效的求解方法,因此将对称的、或者非对称的不定系统转化为对称正定系统就成为解决这类问题的方法之一构造了一类简洁有效的预处理子,将对称不定系统转化为对称正定型,研究了所得预处理系统的谱性质,估计了其谱条件数,推广了现有结论.     

Superlinear PCG Algorithms: Symmetric Part Preconditioning and Boundary Conditions

The superlinear convergence of the preconditioned CGM is studied for nonsymmetric elliptic problems (convection-diffusion equations) with mixed boundary conditions. A mesh independent rate of superlinear convergence is given when symmetric part preconditioning is applied to the FEM discretizations of the BVP. This is the extension of a similar result of the author for Dirichlet problems. The discussion relies on suitably developed Hilbert space theory for linear operators.     

Triangular Witt Groups Part I: The 12-Term Localization Exact Sequence

To a short exact sequence of triangulated categories with duality, we associate a long exact sequence of Witt groups. For this, we introduce higher Witt groups in a very algebraic and explicit way. Since those Witt groups are 4-periodic, this long exact sequence reduces to a cyclic 12-term one. Of course, in addition to higher Witt groups, we need to construct connecting homomorphisms, hereafter called residue homomorphisms.