A fast direct solver for elliptic problems with a divergence constraint

A fast direct solution method for a discretized vector‐valued elliptic partial differential equation with a divergence constraint is considered. Such problems are typical in many disciplines such as fluid dynamics, elasticity and electromagnetics. The method requires the problem to be posed in a rectangle and boundary conditions to be either periodic boundary conditions or the so‐called slip boundary conditions in one co‐ordinate direction. The arising saddle‐point matrix has a separable form when bilinear finite elements are used in the discretization. Based on a result for so‐called p‐circulant matrices, the saddle‐point matrix can be transformed into a block‐diagonal form by fast Fourier transformations. Thus, the fast direct solver has the same structure as methods for scalar‐valued problems which are based on Fourier analysis and, therefore, it has the same computational cost ??(N log N). Numerical experiments demonstrate the good efficiency and accuracy of the proposed method. Copyright © 2002 John Wiley & Sons, Ltd.     

A fast Fourier transform based direct solver for the Helmholtz problem

This article is devoted to the efficient numerical solution of the Helmholtz equation in a two‐ or three‐dimensional (2D or 3D) rectangular domain with an absorbing boundary condition (ABC). The Helmholtz problem is discretized by standard bilinear and trilinear finite elements on an orthogonal mesh yielding a separable system of linear equations. The main key to high performance is to employ the fast Fourier transform (FFT) within a fast direct solver to solve the large separable systems. The computational complexity of the proposed FFT‐based direct solver is $\mathrm{??}(N\log N)$ operations. Numerical results for both 2D and 3D problems are presented confirming the efficiency of the method discussed.     

Fast direct solver for Poisson equation in a 2D elliptical domain

In this article, we extend our previous work 3 for developing some fast Poisson solvers on 2D polar and spherical geometries to an elliptical domain. Instead of solving the equation in an irregular Cartesian geometry, we formulate the equation in elliptical coordinates. The solver relies on representing the solution as a truncated Fourier series, then solving the differential equations of Fourier coefficients by finite difference discretizations. Using a grid by shifting half mesh away from the pole and incorporating the derived numerical boundary value, the difficulty of coordinate singularity can be elevated easily. Unlike the case of 2D disk domain, the present difference equation for each Fourier mode is coupled with its conjugate mode through the numerical boundary value near the pole; thus, those two modes are solved simultaneously. Both second‐ and fourth‐order accurate schemes for Dirichlet and Neumann problems are presented. In particular, the fourth‐order accuracy can be achieved by a three‐point compact stencil which is in contrast to a five‐point long stencil for the disk case. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 72–81, 2004     

A relation between the pressure gradient and the flux for the general channel flow problem

In this paper we establish that the pressure gradient and the flux, for a linear stationary Stokes problem for general periodic two-dimensional channels, are related by a simple formula, the same as that for laminar Poiseuille flows.     

Automated FEM discretizations for the Stokes equation

Current FEM software projects have made significant advances in various automated modeling techniques. We present some of the mathematical abstractions employed by these projects that allow a user to switch between finite elements, linear solvers, mesh refinement and geometry, and weak forms with very few modifications to the code. To evaluate the modularity provided by one of these abstractions, namely switching finite elements, we provide a numerical study based upon the many different discretizations of the Stokes equations. AMS subject classification (2000)  74S05, 65Y99, 35Q30     

A delay differential equation solver based on the parallel Adams algorithms

IntroductionWith the rapid development of science and technology, a lot of delay-dynamic systems invarious fields of natural and social science have arisentl]. The presented delay systems are oftenof both multiparameter and largescale, that is, so-called large systems. Considering scientificcomputation and real-time simulation, the classical serial algorithmsIZ--4] have not fulfilled therequirements for solying this kind of systems. So, it becomes quite emergent to construct thefast algorithm…     

Conditions at infinity for boltzmann's equation.

We consider here realistic conditions at infinity for solutions of the Boltzmann's equation, such as a pure Maxwellian equilibrium at infinity possibly with suitable boundary conditions on an exterior domain, different Maxwellian equilibria at +∞ and -;∞ in a tube-like situation and more generally conditions at infinity obtained from a fixed solution. In order to adapt the recent global existence and compactness results due to R.J. DiPerna and the author, we have to obtain some local a priori estimates on the mass, kinetic energy and entropy. And this is precisely what we achieve here by two different and new methods. The first one consists in using the relative entropy of solutions with respect to a fixed, possibly local, Maxwellian. This method allows to treat general collision kernels with angular cut-off and some of the conditions at infinity mentioned above. The second method is based upon a L¹ estimate and an extension of the entropy identity which uses a truncated H-functional. This method requires a “uniform integrability” condition on the collision kernel but allows to consider the most general conditions at infinity.     

A normalized sparse linear equations solver

Normalized factorization procedures for the solution of large sparse linear finite element systems have been recently introduced in [3]. In these procedures the large sparse symmetric coefficient matrix of irregular structure is factorized exactly to yield a normalized direct solution method. Additionally, approximate factorization procedures yield implicit iterative methods for the finite difference or finite element solution. The numerical implementation of these algorithms is presented here and FORTRAN subroutines for the efficient solution of the resulting large sparse symmetric linear systems of algebraic equations are given.     

A conforming auxiliary space preconditioner for the mass conserving stress-yielding method

We are studying the efficient solution of the system of linear equations stemming from the mass conserving stress-yielding (MCS) discretization of the Stokes equations. We perform static condensation to arrive at a system for the pressure and velocity unknowns. An auxiliary space preconditioner for the positive definite velocity block makes use of efficient and scalable solvers for conforming Finite Element spaces of low order and is analyzed with emphasis placed on robustness in the polynomial degree of the discretization. Numerical experiments demonstrate the potential of this approach and the efficiency of the implementation.     

On a fast direct elliptic solver by a modified Fourier method

We describe high order numerical algorithms for the solution of second order elliptic equations in rectangular domains. These algorithms are based on the Fourier method in combination with a subtraction procedure. The singularities at the corner points, arising due to non-smoothness of the boundaries, are treated explicitly using properly constructed singular corner functions. The present algorithm is a generalization of the Fast Poisson Solver developed in our previous paper. This revised version was published online in August 2006 with corrections to the Cover Date.     

A three-stage, VSVO, Hermite-Birkhoff-Taylor, ODE solver

The new variable-step, variable-order, ODE solver, HBT(p) of order p, presented in this paper, combines a three-stage Runge-Kutta method of order 3 with a Taylor series method of order p-2 to solve initial value problems , where y:R→R^d and f:R×R^d→R^d. The order conditions satisfied by HBT(p) are formulated and they lead to Vandermonde-type linear algebraic systems whose solutions are the coefficients in the formulae for HBT(p). A detailed formulation of variable-step HBT(p) in both fixed-order and variable-order modes is presented. The new method and the Taylor series method have similar regions of absolute stability. To obtain high-accuracy results at high order, this method has been implemented in multiple precision.     

A stable well-conditioned integral equation for electromagnetism scattering

Finding a formulation for electromagnetic scattering of surfaces which is both well-posed and produces a well-conditioned linear system is still a challenging problem. We here propose one such formulation valid in the high-frequency regime. The mathematical analysis is provided and numerical results on rather complex geometries show the performance of the method.     

Multilevel augmentation methods for differential equations

We develop multilevel augmentation methods for solving differential equations. We first establish a theoretical framework for convergence analysis of the boundary value problems of differential equations, and then construct multiscale orthonormal bases in H₀^m(0,1) spaces. Finally, the multilevel augmentation methods in conjunction with the multiscale orthonormal bases are applied to two-point boundary value problems of both second-order and fourth-order differential equations. Theoretical analysis and numerical tests show that these methods are computationally stable, efficient and accurate. Dedicated to Professor Charles A. Micchelli on the occasion of his 60th birthday with friendship and esteem. Mathematics subject classifications (2000) 65J15, 65R20. Zhongying Chen: Supported in part by the Natural Science Foundation of China under grants 10371137 and 10201034, the Foundation of Doctoral Program of National Higher Education of China under grant 20030558008, Guangdong Provincial Natural Science Foundation of China under grant 1011170 and the Foundation of Zhongshan University Advanced Research Center. Yuesheng Xu: Corresponding author. Supported in part by the US National Science Foundation under grants 9973427 and 0312113, by NASA under grant NCC5-399, by the Natural Science Foundation of China under grant 10371122 and by the Chinese Academy of Sciences under the program of “One Hundred Distinguished Young Scientists”.     

A hierarchical basis preconditioner for the biharmonic equation on the sphere

^** Email: jan.maes{at}cs.kuleuven.be In this paper, we propose a natural way to extend a bivariatePowell–Sabin (PS) B-spline basis on a planar polygonaldomain to a PS B-spline basis defined on a subset of the unitsphere in [graphic: see PDF] . The spherical basis inherits many properties of the bivariatebasis such as local support, the partition of unity propertyand stability. This allows us to construct a C¹ continuous hierarchicalbasis on the sphere that is suitable for preconditioning fourth-orderelliptic problems on the sphere. We show that the stiffnessmatrix relative to this hierarchical basis has a logarithmicallygrowing condition number, which is a suboptimal result comparedto standard multigrid methods. Nevertheless, this is a hugeimprovement over solving the discretized system without preconditioning,and its extreme simplicity contributes to its attractiveness.Furthermore, we briefly describe a way to stabilize the hierarchicalbasis with the aid of the lifting scheme. This yields a waveletbasis on the sphere for which we find a uniformly well-conditionedand (quasi-) sparse stiffness matrix.     

A fast multiscale solver for modified Hammerstein equations

This paper presents a fast solver, called the multilevel augmentation method, for modified nonlinear Hammerstein equations. When we utilize the method to solve a large scale problem, most of components of the solution can be computed directly, and lower frequency components can be obtained by solving a fixed low-order algebraic nonlinear system. The advantage of using the algorithm to modified equations is that it leads to reduce the cost of numerical integrations greatly. The optimal error estimate of the method is established and the nearly linear computational complexity is proved. Finally, numerical examples are presented to confirm the theoretical results and illustrate the efficiency of the method.     

Fast direct solvers for Poisson equation on 2D polar and spherical geometries

A simple and efficient class of FFT‐based fast direct solvers for Poisson equation on 2D polar and spherical geometries is presented. These solvers rely on the truncated Fourier series expansion, where the differential equations of the Fourier coefficients are solved by the second‐ and fourth‐order finite difference discretizations. Using a grid by shifting half mesh away from the origin/poles, and incorporating with the symmetry constraint of Fourier coefficients, the coordinate singularities can be easily handled without pole condition. By manipulating the radial mesh width, three different boundary conditions for polar geometry including Dirichlet, Neumann, and Robin conditions can be treated equally well. The new method only needs O(MN log₂ N) arithmetic operations for M × N grid points. © 2002 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 18: 56–68, 2002     

A well-balanced approximate Riemann solver for compressible flows in variable cross-section ducts

A well-balanced approximate Riemann solver is introduced in this paper in order to compute approximations of one-dimensional Euler equations in variable cross-section ducts. The interface Riemann solver is grounded on the VFRoe-ncv scheme, and it enforces the preservation of Riemann invariants of the steady wave. The main properties of the scheme are detailed. We provide numerical results to assess the validity of the scheme, even when the cross-section is discontinuous. A first series is devoted to analytical test cases, and the last results correspond to the simulation of a bubble collapse.     

A direct global superconvergence analysis for Sobolev and viscoelasticity type equations

In this paper we study the finite element approximations to the Sobolev and viscoelasticity type equations and present a direct analysis for global superconvergence for these problems, without using Ritz projection or its modified forms.     

A Jacobi spectral Galerkin method for the integrated forms of fourth‐order elliptic differential equations

This article analyzes the solution of the integrated forms of fourth‐order elliptic differential equations on a rectilinear domain using a spectral Galerkin method. The spatial approximation is based on Jacobi polynomials P (x), with α, β ∈ (?1, ∞) and n the polynomial degree. For α = β, one recovers the ultraspherical polynomials (symmetric Jacobi polynomials) and for α = β = ?½, α = β = 0, the Chebyshev of the first and second kinds and Legendre polynomials respectively; and for the nonsymmetric Jacobi polynomials, the two important special cases α = ?β = ±½ (Chebyshev polynomials of the third and fourth kinds) are also recovered. The two‐dimensional version of the approximations is obtained by tensor products of the one‐dimensional bases. The various matrix systems resulting from these discretizations are carefully investigated, especially their condition number. An algebraic preconditioning yields a condition number of O(N), N being the polynomial degree of approximation, which is an improvement with respect to the well‐known condition number O(N⁸) of spectral methods for biharmonic elliptic operators. The numerical complexity of the solver is proportional to N^d+1 for a d‐dimensional problem. This operational count is the best one can achieve with a spectral method. The numerical results illustrate the theory and constitute a convincing argument for the feasibility of the method. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009