对称正定Toeplitz方程组的多级迭代求解

二级迭代法亦称内外迭代法. 多级迭代法由多个二级迭代嵌套而成.这些方法特别适合于并行计算,同时可以理解为古典迭代法的延伸或共轭梯度法的预处理子.本文讨论了对称正定Toeplitz线性方程组多级迭代法. 首先,基于Toeplitz矩阵的结构, 我们给出了多级块Jacobi分裂,然后证明了每一级分裂均为P-正则分裂, 并证明了当每一级内迭代次数均为偶数时,迭代法的收敛性. 最后通过数值实例验证了此方法的有效性.     

Respectively scaled HSS iteration methods for solving discretized spatial fractional diffusion equations

For the discrete linear systems resulted from the discretization of the one‐dimensional anisotropic spatial fractional diffusion equations of variable coefficients with the shifted finite‐difference formulas of the Grünwald–Letnikov type, we propose a class of respectively scaled Hermitian and skew‐Hermitian splitting iteration method and establish its asymptotic convergence theory. The corresponding induced matrix splitting preconditioner, through further replacements of the involved Toeplitz matrices with certain circulant matrices, leads to an economic variant that can be executed by fast Fourier transforms. Both theoretical analysis and numerical implementations show that this fast respectively scaled Hermitian and skew‐Hermitian splitting preconditioner can significantly improve the computational efficiency of the Krylov subspace iteration methods employed as effective linear solvers for the target discrete linear systems.     

非对称线性方程组的二阶段分裂迭代法

本文针对非对称正定矩阵提出了一个收敛分裂, 给出了分裂收敛的充要条件. 在此基础上, 提出系数为非对称正定矩阵的线性方程组的二阶段算法, 并讨论了算法的收敛条件. 最后, 通过数值例子展示了算法的有效性.     

Applications of the Generalized Fourier Transform in Numerical Linear Algebra

Equivariant matrices, commuting with a group of permutation matrices, are considered. Such matrices typically arise from PDEs and other computational problems where the computational domain exhibits discrete geometrical symmetries. In these cases, group representation theory provides a powerful tool for block diagonalizing the matrix via the Generalized Fourier Transform (GFT). This technique yields substantial computational savings in problems such as solving linear systems, computing eigenvalues and computing analytic matrix functions such as the matrix exponential. The paper is presenting a comprehensive self contained introduction to this field. Building upon the familiar special (finite commutative) case of circulant matrices being diagonalized with the Discrete Fourier Transform, we generalize the classical convolution theorem and diagonalization results to the noncommutative case of block diagonalizing equivariant matrices. Applications of the GFT in problems with domain symmetries have been developed by several authors in a series of papers. In this paper we elaborate upon the results in these papers by emphasizing the connection between equivariant matrices, block group algebras and noncommutative convolutions. Furthermore, we describe the algebraic structure of projections related to non-free group actions. This approach highlights the role of the underlying mathematical structures, and provides insight useful both for software construction and numerical analysis. The theory is illustrated with a selection of numerical examples. AMS subject classification (2000) 43A30, 65T99, 20B25     

General construction of symmetric parabolic structures

First we introduce a generalization of symmetric spaces to parabolic geometries. We provide construction of such parabolic geometries starting with classical symmetric spaces and we show that all regular parabolic geometries with smooth systems of involutive symmetries can be obtained in this way. Further, we investigate the case of parabolic contact geometries in great detail and we provide the full classification of those with semisimple groups of symmetries without complex factors. Finally, we explicitly construct all non-trivial contact geometries with non-complex simple groups of symmetries. We also indicate geometric interpretations of some of them.     

Symmetries of parabolic geometries

We generalize the concept of affine locally symmetric spaces for parabolic geometries. We discuss mainly |1|-graded geometries and we show some restrictions on their curvature coming from the existence of symmetries. We use the theory of Weyl structures to discuss more interesting |1|-graded geometries which can carry a symmetry in a point with nonzero curvature. More concretely, we discuss the number of different symmetries which can exist at the point with nonzero curvature.     

A two-step matrix splitting iteration paradigm based on one single splitting for solving systems of linear equations

For solving large sparse systems of linear equations, we construct a paradigm of two-step matrix splitting iteration methods and analyze its convergence property for the nonsingular and the positive-definite matrix class. This two-step matrix splitting iteration paradigm adopts only one single splitting of the coefficient matrix, together with several arbitrary iteration parameters. Hence, it can be constructed easily in actual applications, and can also recover a number of representatives of the existing two-step matrix splitting iteration methods. This result provides systematic treatment for the two-step matrix splitting iteration methods, establishes rigorous theory for their asymptotic convergence, and enriches algorithmic family of the linear iteration solvers, for the iterative solutions of large sparse linear systems.     

Chu duality theory and coalgebraic representation of quantum symmetries

Building upon Vaughan Pratt's work on applications of Chu space theory to Stone duality, we develop a general theory of categorical dualities on the basis of Chu space theory and closure conditions, which encompasses a variety of dualities for topological spaces, convex spaces, closure spaces, and measurable spaces (some of which are new duality results on their own). It works as a general method to generate analogues of categorical dualities between frames (locales) and topological spaces beyond topology, e.g., for measurable spaces, convex spaces, and closure spaces. After establishing the Chu duality theory, we apply the state-observable duality between quantum lattices and closure spaces to coalgebraic representations of quantum symmetries, showing that the quantum symmetry groupoid fully embeds into a purely coalgebraic category, i.e., the category of Born coalgebras, which refines, through the quantum duality that follows from Chu duality theory, Samson Abramsky's fibred coalgebraic representations of quantum symmetries (which, in turn, builds upon his Chu representations of symmetries).     

A reduced model to locate low contrast inclusions in poroelastic media

This paper introduces a numerical method to localize inclusions having slightly different elastic coefficients than those of a fully saturated poroelastic matrix, whose detection is often difficult. This method can be used to find weakly stiffer or softer objects in saturated soils or diseased biological tissues at early stages. To this end, we propose a reduced model from the Biot’s equations by splitting the fluid pressure into two parts: one embedded into an elasticity model and the other one used as a corrector term. By applying the small amplitude homogenization method, we can successfully retrieve the position and extension of inclusions in poroelastic media employing this simplified model. Numerical results show a good agreement for the location of inclusions when the contrast is below 30% stiffer or softer than the matrix, and for a noise level up to 5% for frequencies below 50 Hz.     

Three-level schemes of the alternating triangular method

In this paper, the schemes of the alternating triangular method are set out in the class of splitting methods used for the approximate solution of Cauchy problems for evolutionary problems. These schemes are based on splitting the problem operator into two operators that are conjugate transposes of each other. Economical schemes for the numerical solution of boundary value problems for parabolic equations are designed on the basis of an explicit-implicit splitting of the problem operator. The alternating triangular method is also of interest for the construction of numerical algorithms that solve boundary value problems for systems of partial differential equations and vector systems. The conventional schemes of the alternating triangular method used for first-order evolutionary equations are two-level ones. The approximation properties of such splitting methods can be improved by transiting to three-level schemes. Their construction is based on a general principle for improving the properties of difference schemes, namely, on the regularization principle of A.A. Samarskii. The analysis conducted in this paper is based on the general stability (or correctness) theory of operator-difference schemes.     

Operator-splitting methods via the Zassenhaus product formula

In this paper, we contribute an operator-splitting method improved by the Zassenhaus product. Zassenhaus products are of fundamental importance for the theory of Lie groups and Lie algebras. While their applications in physics and physical chemistry are important, novel applications in CFD (computational fluid dynamics) arose based on the fact that their sparse matrices can be seen as generators of an underlying Lie algebra. We apply this to classical splitting and the novel Zassenhaus product formula. The underlying analysis for obtaining higher order operator-splitting methods based on the Zassenhaus product is presented. The benefits of dealing with sparse matrices, given by spatial discretization of the underlying partial differential equations, are due to the fact that the higher order commutators are very quickly computable (their matrix structures thin out and become nilpotent). When applying these methods to convection-diffusion-reaction equations, the benefits of balancing time and spatial scales can be used to accelerate these methods and take into account these sparse matrix structures.The verification of the improved splitting methods is done with numerical examples. Finally, we conclude with higher order operator-splitting methods.     

The modulus‐based matrix splitting algorithms for a class of weakly nonlinear complementarity problems

In this paper, we study a class of weakly nonlinear complementarity problems arising from the discretization of free boundary problems. By reformulating the complementarity problems as implicit fixed‐point equations based on splitting of the system matrices, we propose a class of modulus‐based matrix splitting algorithms. We show their convergence by assuming that the system matrix is positive definite. Moreover, we give several kinds of typical practical choices of the modulus‐based matrix splitting iteration methods based on the different splitting of the system matrix. Numerical experiments on two model problems are presented to illustrate the theoretical results and examine the numerical effectiveness of our modulus‐based matrix splitting algorithms. Copyright © 2016 John Wiley & Sons, Ltd.     

Symmetries of Quantum Lax Equations for the Painlevé Equations

Based on the fact that the Painlevé equations can be written as Hamiltonian systems with affine Weyl group symmetries, a canonical quantization of the Painlevé equations preserving such symmetries has been studied recently. On the other hand, since the Painlevé equations can also be described as isomonodromic deformations of certain second-order linear differential equations, a quantization of such Lax formalism is also a natural problem. In this paper, we introduce a canonical quantization of Lax equations for the Painlevé equations and study their symmetries. We also show that our quantum Lax equations are derived from Virasoro conformal field theory.     

On multisplitting methods for band matrices

Summary. We present new theoretical results on two classes of multisplitting methods for solving linear systems iteratively. These classes are based on overlapping blocks of the underlying coefficient matrix which is assumed to be a band matrix. We show that under suitable conditions the spectral radius of the iteration matrix does not depend on the weights of the method even if these weights are allowed to be negative. For a certain class of splittings we prove an optimality result for with respect to the weights provided that is an M–matrix. This result is based on the fact that the multisplitting method can be represented by a single splitting which in our situation surprisingly turns out to be a regular splitting. Furthermore we show by numerical examples that weighting factors may considerably improve the convergence. Received July 18, 1994 / Revised version received November 20, 1995     

Convergences of splitting iterative methods for symmetric indefinite linear systems

In this paper, we generalize the saddle point problem to general symmetric indefinite systems, we also present a kind of convergent splitting iterative methods for the symmetric indefinite systems. A special divergent splitting is introduced. The sufficient condition is discussed that the eigenvalues of the iteration matrix are real. The spectral radius of the iteration matrix is discussed in detail, the convergence theories of the splitting iterative methods for the symmetric indefinite systems are obtained. Finally, we present a preconditioner and discuss the eigenvalues of preconditioned matrix.     

A preconditioned general modulus-based matrix splitting iteration method for linear complementarity problems of <Emphasis Type="Italic">H</Emphasis>-matrices

In this paper, we propose a preconditioned general modulus-based matrix splitting iteration method for solving modulus equations arising from linear complementarity problems. Its convergence theory is proved when the system matrix is an H₊-matrix, from which some new convergence conditions can be derived for the (general) modulus-based matrix splitting iteration methods. Numerical results further show that the proposed methods are superior to the existing methods.     

Application of homotopy perturbation methods for solving systems of linear equations

In this paper, homotopy perturbation methods (HPMs) are applied to obtain the solution of linear systems, and conditions are deduced to check the convergence of the homotopy series. Moreover, we have adapted the Richardson method, the Jacobi method, and the Gauss-Seidel method to choose the splitting matrix. The numerical results indicate that the homotopy series converges much more rapidly than the direct methods for large sparse linear systems with a small spectrum radius.     

A splitting preconditioner for implicit Runge-Kutta discretizations of a partial differential-algebraic equation

In this paper we study efficient iterative methods for solving the system of linear equations arising from the fully implicit Runge-Kutta discretizations of a class of partial differential-algebraic equations. In each step of the time integration, a block two-by-two linear system is obtained and needed to be solved numerically. A preconditioning strategy based on an alternating Kronecker product splitting of the coefficient matrix is proposed to solve such linear systems. Some spectral properties of the preconditioned matrix are established and numerical examples are presented to demonstrate the effectiveness of this approach.     

求解时谐涡流模型鞍点问题的分块交替分裂隐式迭代算法的改进

分块交替分裂隐式迭代方法是求解具有鞍点结构的复线性代数方程组的一类高效迭代法.本文通过预处理技巧得到原方法的一种加速改进方法,称之为预处理分块交替分裂隐式迭代方法·理论分析给出了新方法的收敛性结果.对于一类时谐涡旋电流模型问题,我们给出了若干满足收敛条件的迭代格式.数值实验验证了新型算法是对原方法的有效改进.     

Bifurcation from periodic solutions with spatiotemporal symmetry, including resonances and mode interactions

We study local bifurcation in equivariant dynamical systems from periodic solutions with a mixture of spatial and spatiotemporal symmetries.In previous work, we focused primarily on codimension one bifurcations. In this paper, we show that the techniques used in the codimension one analysis can be extended to understand also higher codimension bifurcations, including resonant bifurcations and mode interactions. In particular, we present a general reduction scheme by which we relate bifurcations from periodic solutions to bifurcations from fixed points of twisted equivariant diffeomorphisms, which in turn are linked via normal form theory to bifurcations from equilibria of equivariant vector fields.We also obtain a general theory for bifurcation from relative periodic solutions and we show how to incorporate time-reversal symmetries into our framework.