High order projection methods of moment- and collocation-type for nonlinear boundary value problems

Approximations to an isolated solution of a two point boundary value problem are determined by projection methods with piecewise polynomial functions. Some principles are derived which lead in a uniform way to statements of high-order convergence for a variety of moment-type methods and collocation methods with Gaussian nodes.     

大规模有限元刚度矩阵存储及其并行求解算法

本文提出一种将有限元单元刚度矩阵直接集成压缩格式的总体刚度矩阵的方法,并针对其线性系统设计了预处理的重启动GMRES(m)并行求解器.集成方法使用了一个“关联结点”的数据结构,它用来记录网格中节点的关联信息,作为集成过程的中间媒介.这种方法能减少大量的存储空间,简单且高效.求解器分别使用Jacobi和稀疏近似逆(SPAI)预条件子.二维和三维弹性力学问题的数值试验表明,在二维情形下,SPAI预条件子具有很好的加速收敛效果和并行效率;在三维情形下,Jacobi预条件子更能减少迭代收敛时间.     

On relaxed nested factorization and combination preconditioning

The efficient solution of block tridiagonal linear systems arising from the discretization of convection–diffusion problem is considered in this paper. Starting with the classical nested factorization, we propose a relaxed nested factorization preconditioner. Then, several combination preconditioners are developed based on relaxed nested factorization and a tangential filtering preconditioner. Influence of the relaxation parameter is numerically studied, the results indicate that the optimal relaxation parameter should be close to but less than 1. The number of iteration counts exhibit an extremely sensitive behaviour. This phenomena resembles the behaviour of relaxed ILU preconditioner. For symmetric positive-definite coefficient matrix, we also show that the proposed combination preconditioner is convergent. Finally, numerous test cases are carried out with both additive and multiplicative combinations to verify the robustness of the proposed preconditioners.     

Additive polynomial preconditioners for parallel computers

We present a polynomial preconditioner that can be used with the conjugate gradient method to solve symmetric and positive definite systems of linear equations. Each step of the preconditioning is achieved by simultaneously taking an iteration of the SOR method and an iteration of the reverse SOR method (equations taken in reverse order) and averaging the results. This yields a symmetric preconditioner that can be implemented on parallel computers by performing the forward and reverse SOR iterations simultaneously. We give necessary and sufficient conditions for additive preconditioners to be positive definite.

We find an optimal parameter, ω, for the SOR-Additive linear stationary iterative method applied to 2-cyclic matrices. We show this method is asymptotically twice as fast as SSOR when the optimal ω is used.

We compare our preconditioner to the SSOR polynomial preconditioner for a model problem. With the optimal ω, our preconditioner was found to be as effective as the SSOR polynomial preconditioner in reducing the number of conjugate gradient iterations. Parallel implementations of both methods are discussed for vector and multiple processors. Results show that if the same number of processors are used for both preconditioners, the SSOR preconditioner is more effective. If twice as many processors are used for the SOR-Additive preconditioner, it becomes more efficient than the SSOR preconditioner when the number of equations assigned to a processor is small. These results are confirmed by the Blue Chip emulator at the University of Washington.     

The hierarchial preconditioning on unstructured grids

We present the implementation of two hierarchically preconditioned methods for the fast solution of mesh equations that approximate 2D-elliptic boundary value problems on unstructured quasi uniform triangulations. Based on the fictitious space approach the original problem can be embedded into an auxiliary one, where both the hierarchical grid information and the preconditioner are well defined. We implemented the corresponding Yserentant preconditioned conjugate gradient method as well as thebpx-preconditioned cg-iteration having optimal computational costs. Several numerical examples demonstrate the efficiency of the artificially constructed hierarchical methods which can be of importance in industrial engineering, where often only the nodal coordinates and the element connectivity of the underlying (fine) discretization are available.     

一类具有未知幂次的高阶不确定非线性系统的自适应控制

研究了一类具有未知幂次的高阶不确定非线性系统的自适应跟踪控制问题.在无需系统函数先验知识的条件下,采用积分反推技术和障碍李雅普诺夫函数,提出了一种新颖的自适应跟踪控制算法.该控制算法的显著特点是所设计的自适应控制器均与系统幂次无关,并且能够保证闭环系统的所有信号皆有界.仿真算例验证了该控制算法的有效性.     

Circulant block-factorization preconditioners for elliptic problems

New circulant block-factorization preconditioners are introduced and studied. The general approach is first formulated for the case of block tridiagonal sparse matrices. Then estimates of the relative condition number for a model Dirichlet boundary value problem are derived. In the case ofy-periodic problems the circulant block-factorization preconditioner is shown to give an optimal convergence rate. Finally, using a proper imbedding of the original Dirichlet boundary value problem to ay-periodic one a preconditioner of optimal convergence rate for the general case is obtained. The total computational cost of the preconditioner isO (N logN) (based on FFT), whereN is the number of unknowns. That is, the algorithm is nearly optimal. Various numerical tests that demonstrate the features of the circulant block-factorization preconditioners are presented.     

High-Order Convergence of Spectral Deferred Correction Methods on General Quadrature Nodes

It has been demonstrated that spectral deferred correction (SDC) methods can achieve arbitrary high order accuracy and possess good stability properties. There have been some recent interests in using high-order Runge-Kutta methods in the prediction and correction steps in the SDC methods, and higher order rate of convergence is obtained provided that the quadrature nodes are uniform. The assumption of the use of uniform mesh has a serious practical drawback as the well-known Runge phenomenon may prevent the use of reasonably large number of quadrature nodes. In this work, we propose a modified SDC methods with high-order integrators which can yield higher convergence rates on both uniform and non-uniform quadrature nodes. The expected high-order of accuracy is theoretically verified and numerically demonstrated.     

Boundary value methods with the Crank–Nicolson preconditioner for pricing options in the jump-diffusion model

Under a jump-diffusion process, the option pricing function satisfies a partial integro-differential equation. A fourth-order compact scheme is used to discretize the spatial variable of this equation. The boundary value method is then utilized for temporal integration because of its unconditional stability and high-order accuracy. Two approaches, the local mesh refinement and the start-up procedure with refined step size, are raised to avoid the numerical malfunction brought by the nonsmooth payoff function. The GMRES method with a preconditioner which comes from the Crank–Nicolson formula is employed to solve the resulting large-scale linear system. Numerical experiments demonstrate the efficiency of the proposed method when pricing European and double barrier call options in the jump-diffusion model.     

一种求解H(curl)型椭圆问题的高效并行预条件子及并行实现

本文为一类H(curl)型椭圆问题的线性棱有限元方程,构造了一种基于节点辅助空间预条件子(HX预条件子)和基于简单粗空间的非重叠区域分解相结合的预条件子,并为该预条件子设计了并行算法,编制了基于MPI+OpenMP二级并行架构的并行程序.数值实验结果表明基于该预条件子的并行PCG法具有良好的算法可扩展能力和并行可扩展能力.     

A preconditioner for the Schur complement matrix

A preconditioner for iterative solution of the interface problem in Schur Complement Domain Decomposition Methods is presented. This preconditioner is based on solving a global problem in a narrow strip around the interface. It requires much less memory and computing time than classical Neumann–Neumann preconditioner and its variants, and handles correctly the flux splitting among subdomains that share the interface. The aim of this work is to present a theoretical basis (regarding the behavior of Schur complement matrix spectra) and some simple numerical experiments conducted in a sequential environment as a motivation for adopting the proposed preconditioner. Efficiency, scalability, and implementation details on a production parallel finite element code [Sonzogni V, Yommi A, Nigro N, Storti M. A parallel finite element program on a Beowulf cluster. Adv Eng Software 2002;33(7–10):427–43; Storti M, Nigro N, Paz R, Dalcín L. PETSc-FEM: a general purpose, parallel, multi-physics FEM program, 1999–2006] can be found in works [Paz R, Storti M. An interface strip preconditioner for domain decomposition methods: application to hydrology. Int J Numer Methods Eng 2005;62(13):1873–94; Paz R, Nigro N, Storti M. On the efficiency and quality of numerical solutions in cfd problems using the interface strip preconditioner for domain decomposition methods. Int J Numer Methods Fluids, in press].     

Structure Preserving Preconditioners for Image Deblurring

Regularizing preconditioners for accelerating the convergence of iterative regularization methods without spoiling the quality of the approximated solution have been extensively investigated in the last twenty years. Several strategies have been proposed for defining proper preconditioners. Usually, in methods for image restoration, the structure of the preconditioner is chosen Block Circulant with Circulant Blocks (BCCB) because it can be efficiently exploited by Fast Fourier Transform (FFT). Nevertheless, for ill-conditioned problems, it is well-known that BCCB preconditioners cannot provide a strong clustering of the eigenvalues. Moreover, in order to get an effective preconditioner, it is crucial to preserve the structure of the coefficient matrix. The structure of such a matrix, in case of image deblurring problem, depends on the boundary conditions imposed on the imaging model. Therefore, we propose a technique to construct a preconditioner which has the same structure of the blurring matrix related to the restoration problem at hand. The construction of our preconditioner requires two FFTs like the BCCB preconditioner. The presented preconditioning strategy represents a generalization and an improvement with respect to both circulant and structured preconditioning available in the literature. The technique is further extended to provide a non-stationary preconditioning in the same spirit of a recent proposal for BCCB matrices. Some numerical results show the importance of preserving the matrix structure from the point of view of both restoration quality and robustness of the regularization parameter.     

BDDC preconditioning for high-order Galerkin Least-Squares methods using inexact solvers

A high-order Galerkin Least-Squares (GLS) finite element discretization is combined with a Balancing Domain Decomposition by Constraints (BDDC) preconditioner and inexact local solvers to provide an efficient solution technique for large-scale, convection-dominated problems. The algorithm is applied to the linear system arising from the discretization of the two-dimensional advection–diffusion equation and Euler equations for compressible, inviscid flow. A Robin–Robin interface condition is extended to the Euler equations using entropy-symmetrized variables. The BDDC method maintains scalability for the high-order discretization of the diffusion-dominated flows, and achieves low iteration count in the advection-dominated regime. The BDDC method based on inexact local solvers with incomplete factorization and p = 1 coarse correction maintains the performance of the exact counterpart for the wide range of the Peclet numbers considered while at significantly reduced memory and computational costs.     

Physically based adaptive preconditioning for early vision

Several problems in early vision have been formulated in the past in a regularization framework. These problems, when discretized, lead to large sparse linear systems. In this paper, we present a novel physically based adaptive preconditioning technique which can be used in conjunction with a conjugate gradient algorithm to dramatically improve the speed of convergence for solving the aforementioned linear systems. A preconditioner, based on the membrane spline, or the thin plate spline, or a convex combination of the two, is termed a physically based preconditioner for obvious reasons. The adaptation of the preconditioner to an early vision problem is achieved via the explicit use of the spectral characteristics of the regularization filter in conjunction with the data. This spectral function is used to modulate the frequency characteristics of a chosen wavelet basis, and these modulated values are then used in the construction of our preconditioner. We present the preconditioner construction for three different early vision problems namely, the surface reconstruction, the shape from shading, and the optical flow computation problems. Performance of the preconditioning scheme is demonstrated via experiments on synthetic and real data sets     

Domain decomposition PCG methods for serial and parallel processing

In this paper two domain decomposition formulations are presented in conjunction with the preconditioned conjugate gradient method (PCG) for the solution of large-scale problems in solid and structural mechanics. In the first approach, the PCG method is applied to the global coefficient matrix, while in the second approach it is applied to the interface problem after eliminating the internal degrees of freedom. For both implementations, a subdomain-by-subdomain (SBS) polynomial preconditioner is employed, based on local information of each subdomain. The approximate inverse of the global coefficient matrix or the Schur complement matrix, which acts as the preconditioner, is expressed by a truncated Neumann series resulting in an additive type local preconditioner. Block type preconditioning, where full elimination is performed inside each block, is also studied and compared with the proposed polynomial preconditioning.     

A partial preconditioned conjugate gradient method for large eigenproblems

In this paper a preconditioned iterative method suitable for the solution of the generalized eigenvalue problem Ax = λBx is presented. The proposed method is suitable for the determination of extreme eigenvalues and their corresponding eigenvectors of large sparse eigenproblems derived from the finite element discretization method. The solution is obtained through the minimization of the Rayleigh quotient by a preconditioned conjugate gradient (CG) method. The proposed triangular splitting preconditioner combines Evans' SSOR preconditioner with a drop-off tolerance criterion and is called partial preconditioner (PPR). The PPR is attractive in a large FE framework because it is simple and can be implemented at the element level, as opposed to incomplete Choleski preconditioners, which require a sparse assembly. Because of the renewed interest in CG techniques for FE work on microprocessors and parallel computers it is believed that this improved approach to the generalized eigenvalue problem, through the minimization of the Rayleigh quotient, is likely to be very promising.     

基于样本空间学习算法的彩色匹配方法研究

提出基于样本空间学习箅法的RGB(Red,Green,Blue)→CMYK(Cyan, Magenta,Yellow,blacK)颜色空间变换方法,仅需测试400组纯色色块,即可在不同的打印 (抖动)模式、墨水和纸张条件下,对RGB→CMYK转换规律进行有效的学习.该算法学习能 力强、打印速度快,通过在模型中增加高次项,提高了彩色匹配的精度,进一步解决了彩色匹 配的自动化和通用性问题.同时,借助于CIELab均匀颜色空间对图像进行动态范围调整,还 起到了减小色偏、突出图像细节、增强图像对比度的效果.     

板问题预条件子在曙光D1000+上的MPI实现

１．引言 在求解由偏微分方程引出的大规模线性系统时,多水平方法已经成为强有力的工具．多水平预条件子的构造在理论上已有大量的文献［１,４,８－１２］．在对多水平预条件子构造时,一般需要嵌套的网格和空间,这对高阶有限元和非协调元来说是十分困难的．许学军在其博士论文中［７］通过引入辅助的嵌套的低阶有限元空间（四阶问题为ＢＦＳ和ＰＳ元）和插值算子来解决这个问题,构造了最优的预条件子（相似的构造见［１０］）． 一般地,对于大规模的线性系统,我们不用直接法求解,而是用共轭梯度法等迭代方法求解［３］．当用 ＣＧ…     

High-order accurate computations for unsteady aerodynamics

A high-order accurate finite difference scheme is used to perform numerical studies on the benefit of high-order methods. The main advantage of the present technique is the possibility to prove stability for the linearized Euler equations on a multi-block domain, including the boundary conditions. The result is a robust high-order scheme for realistic applications. Convergence studies are presented, verifying design order of accuracy and the superior efficiency of high-order methods for applications dominated by wave propagation. Furthermore, numerical computations of a more complex problem, a vortex-airfoil interaction, show that high-order methods are necessary to capture the significant flow features for transient problems and realistic grid resolutions. This methodology is easy to parallelize due to the multi-block capability. Indeed, we show that the speedup of our numerical method scales almost linearly with the number of processors.     

High-order consensus of heterogeneous multi-agent systems with unknown communication delays

This paper studies the high-order consensus problem for heterogeneous multi-agent systems with unknown communication delays. A necessary and sufficient condition is given for the existence of a high-order consensus solution to heterogeneous multi-agent systems. The condition shows that, for systems with diverse communication delays, high-order consensus does not require the self-delay of each agent to be equal to the corresponding communication delay. When the communication delays are unknown, a simple adaptive adjustment algorithm is presented for on-line adjusting self-delays.