An incomplete factorization preconditioning method based on modification of element matrices

It is well known that standard incomplete factorization (IC) methods exist for M-matrices [15] and that modified incomplete factorization (MIC) methods exist for weakly diagonally dominant matrices [8]. The restriction to these classes of matrices excludes many realistic general applications to discretized partial differential equations. We present a technique to avoid this problem by making an initial modification already at the element level, followed by the standard IC or MIC factorization of the assembled matrix. This modification ensures weakly diagonally dominant M-matrices and is made in such a way that the condition number of the matrix is only increased by a constant factor independent of the mesh parameterh. Hence the fast convergence of the MICCG method, that is inO(h ^–1/2),h 0 iterations for second order elliptic problems, is preserved.     

Detailed Error Analysis for a Fractional Adams Method

We investigate a method for the numerical solution of the nonlinear fractional differential equation D _* y(t)=f(t,y(t)), equipped with initial conditions y ^(k)(0)=y ₀ ^(k), k=0,1,...,–1. Here may be an arbitrary positive real number, and the differential operator is the Caputo derivative. The numerical method can be seen as a generalization of the classical one-step Adams–Bashforth–Moulton scheme for first-order equations. We give a detailed error analysis for this algorithm. This includes, in particular, error bounds under various types of assumptions on the equation. Asymptotic expansions for the error are also mentioned briefly. The latter may be used in connection with Richardson's extrapolation principle to obtain modified versions of the algorithm that exhibit faster convergence behaviour.     

A relative compactness criterion in Wiener–Sobolev spaces and application to semi-linear Stochastic PDEs

We prove a relative compactness criterion in Wiener–Sobolev space which represents a natural extension of the compact embedding of Sobolev space H¹ into , at the level of random fields. Then we give a specific statement of this criterion for random fields solutions of semi-linear stochastic partial differential equations with coefficients bounded in an appropriate way. Finally, we employ this result to construct solutions for semi-linear stochastic partial differential equations with distribution as final condition. We also give a probabilistic interpretation of this solution in terms of backward doubly stochastic differential equations formulated in a weak sense.     

Convergence of an iterative algorithm for solving Hamilton-Jacobi type equations

Solutions of the optimal control and -control problems for nonlinear affine systems can be found by solving Hamilton-Jacobi equations. However, these first order nonlinear partial differential equations can, in general, not be solved analytically. This paper studies the rate of convergence of an iterative algorithm which solves these equations numerically for points near the origin. It is shown that the procedure converges to the stabilizing solution exponentially with respect to the iteration variable. Illustrative examples are presented which confirm the theoretical rate of convergence.

     

On the Wl q-Regularity of Solutions to Systems of Differential Equations in the Case When the Equations Are Constructed from Discontinuous Functions

Some solution, final in a sense from the standpoint of the theory of Sobolev spaces, is obtained to the problem of regularity of solutions to a system of (generally) nonlinear partial differential equations in the case when the system is locally close to elliptic systems of linear equations with constant coefficients. The main consequences of this result are Theorems 5 and 8. According to the first of them, the higher derivatives of an elliptic C ^l -smooth solution to a system of lth-order nonlinear partial differential equations constructed from C ^l -smooth functions meet the local Hoelder condition with every exponent , 0<<1. Theorem 8 claims that if a system of linear partial differential equations of order l with measurable coefficients and right-hand sides is uniformly elliptic then, under the hypothesis of a (sufficiently) slow variation of its leading coefficients, the degree of local integrability of lth-order partial derivatives of every W ^l _q,loc-solution, q>1, to the system coincides with the degree of local integrability of lower coefficients and right-hand sides.     

Classification of nonlocal boundary-value problems on a narrow strip

For a general linear partial differential equation with constant coefficients, we establish a well-posedness criterion for a boundary-value problem on a strip _y= × [0,Y] with an integral in a boundary condition. A complete classification of such problems based on their asymptotic properties asY 0 is obtained.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 4, pp. 338–346, April, 1994.     

Solution of nonsymmetric linear complementarity problems by iterative methods

Convergence is established for iterative algorithms for the solution of the nonsymmetric linear complementarity problem of findingz such thatMz+q0,z0,z ^T(Mz+q)=0, whereM is a givenn×n real matrix, not necessarily symmeetric, andq is a givenn-vector. It is first shown that, if the spectral radius of a matrix related toM is less than one, then the iterates generated by the general algorithm converge to a solution of the linear complementarity problem. It turns out that convergence properties are quite similar to those of linear systems of equations. As specific cases, two important classes of matrices, Minkowski matrices and quasi-dominant diagonal matrices, are shown to satisfy this convergence condition.The author is grateful to Professor O. L. Mangasarian and the referees for their substantive suggestions and corrections.     

Fourier-Galerkin Method for Localized Solutions of Equations with Cubic Nonlinearity

Using a complete orthonormal system of functions in L ²(– ,) a Fourier-Galerkin spectral technique is developed for computing of the localized solutions of equations with cubic nonlinearity. A formula expressing the triple product into series in the system is derived. Iterative algorithm implementing the spectral method is developed and tested on the soliton problem for the cubic Boussinesq equation. Solution is obtained and shown to compare quantitatively very well to the known analytical one. The issues of convergence rate and truncation error are discussed.     

Convergence of centered difference schemes for a system of two-dimensional equations of acoustics

The accuracy of difference schemes for first-order hyperbolic systems is studied for the case of two-dimensional equations of acoustics with various boundary conditions. A difference scheme is constructed and an a priori bound of the error is obtained in some weak norm. This bound combined with the Bramble-Hilbert theorem makes it possible to prove o(^m + h^m) convergence of the difference solution to the solution of the differential problem in the class W₂ ^m(Q_T, m=1,2.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 57, pp. 48–57, 1985.     

Convergence properties of the Runge-Kutta-Chebyshev method

Summary The Runge-Kutta-Chebyshev method is ans-stage Runge-Kutta method designed for the explicit integration of stiff systems of ordinary differential equations originating from spatial discretization of parabolic partial differential equations (method of lines). The method possesses an extended real stability interval with a length proportional tos ². The method can be applied withs arbitrarily large, which is an attractive feature due to the proportionality of withs ². The involved stability property here is internal stability. Internal stability has to do with the propagation of errors over the stages within one single integration step. This internal stability property plays an important role in our examination of full convergence properties of a class of 1st and 2nd order schemes. Full convergence means convergence of the fully discrete solution to the solution of the partial differential equation upon simultaneous space-time grid refinement. For a model class of linear problems we prove convergence under the sole condition that the necessary time-step restriction for stability is satisfied. These error bounds are valid for anys and independent of the stiffness of the problem. Numerical examples are given to illustrate the theoretical results.Dedicated to Peter van der Houwen for his numerous contributions in the field of numerical integration of differential equations.Paper presented at the symposium Construction of Stable Numerical Methods for Differential and Integral Equations, held at CWI, March 29, 1989, in honor of Prof. Dr. P.J. van der Houwen to celebrate the twenty-fifth anniversary of his stay at CWI     

Parallel linear system solvers for Runge-Kutta methods

If the nonlinear systems arising in implicit Runge-Kutta methods like the Radau IIA methods are iterated by (modified) Newton, then we have to solve linear systems whose matrix of coefficients is of the form I-A hJ with A the Runge-Kutta matrix and J an approximation to the Jacobian of the righthand side function of the system of differential equations. For larger systems of differential equations, the solution of these linear systems by a direct linear solver is very costly, mainly because of the LU-decompositions. We try to reduce these costs by solving the linear systems by a second (inner) iteration process. This inner iteration process is such that each inner iteration again requires the solution of a linear system. However, the matrix of coefficients in these new linear systems is of the form I - B hJ where B is similar to a diagonal matrix with positive diagonal entries. Hence, after performing a similarity transformation, the linear systems are decoupled into s subsystems, so that the costs of the LU-decomposition are reduced to the costs of s LU-decompositions of dimension d. Since these LU-decompositions can be computed in parallel, the effective LU-costs on a parallel computer system are reduced by a factor s ³ . It will be shown that matrices B can be constructed such that the inner iterations converge whenever A and J have their eigenvalues in the positive and nonpositive halfplane, respectively. The theoretical results will be illustrated by a few numerical examples. A parallel implementation on the four-processor Cray-C98/4256 shows a speed-up ranging from at least 2.4 until at least 3.1 with respect to RADAU5 applied in one-processor mode.     

The numerical solution of Fredholm integral equations of the second kind with singular kernels

A numerical method is given for integral equations with singular kernels. The method modifies the ideas of product integration contained in [3], and it is analyzed using the general schema of [1]. The emphasis is on equations which were not amenable to the method in [3]; in addition, the method tries to keep computer running time to a minimum, while maintaining an adequate order of convergence. The method is illustrated extensively with an integral equation reformulation of boundary value problems for u–P(r ²)u=0; see [9].This research was supported in part by NSF grant GP-8554.     

Theh−p version of the finite element method for elliptic equations of order2m

Summary The problems of elliptic partial differential equations stemming from engineering problems are usually characterized by piecewise analytic data. It has been shown in [3, 4, 5] that the solutions of the second order and fourth order equations belong to the spacesB ¹ where the weighted Sobolev norms of thek-th derivatives are bounded byCd ^k–l (k–l)!,kl, l2 whereC andd are constants independent ofk. In this case theh–p version of the finite element method leads to an exponential rate of convergence measured in the energy norm [6, 12, 13]. Theh–p version was implemented in the code PROBE¹ [18] and has been very successfully used in the industry.We will discuss in this paper the generalization of these results for problems of order2m. We will show also that the exponential rate can be achieved if the exact solution belongs to the spacesB ¹ where the weighted Sobolev norm of thek-th derivatives is bounded byCd ^k–l (k–l)!,kl=m+1, C andd are independent ofk. In addition, if the data is piecewise analytic, then in fact the exact solution belongs to the spacesB ^m+1 .Problems of this type are related obviously to many engineering problems, such as problems of plates and shells, and are also important in connection with well-known locking problems.Dedicated to Professor Ivo Babuka on the occasion of his 60^th birthdaySupported by the Air Force Office of Science Research under grant No. AFOSR-80-0277 NOETIC TECHNOLOGIES, Inc., St. Louis, MO     

On the approximation of singular integral equations by equations with smooth kernels

Singular integral equations with Cauchy kernel and piecewise-continuous matrix coefficients on open and closed smooth curves are replaced by integral equations with smooth kernels of the form(t–)[(t–) ²–n ² (t) ²]^–1,0, wheren(t), t , is a continuous field of unit vectors non-tangential to . we give necessary and sufficient conditions under which the approximating equations have unique solutions and these solutions converge to the solution of the original equation. For the scalar case and the spaceL ₂() these conditions coincide with the strong ellipticity of the given equation.This work was fulfilled during the first author's visit to the Weierstrass Institute for Applied Analysis and Stochastics, Berlin in October 1993.     

Partial integrals and the first focal value in the problem of centre

Polynomial differential systems of degreen3 on the plane are investigated. It is assumed that the originO(0, 0) is a critical point with imaginary eigenvalues. We show that if the first focal value vanishes and there existN=(n²+n–4)/2 partial algebraical integrals then the origin is a centre. For cubic systems (n=3), we have obtained fourteen series of conditions each ensuring that the origin is a centre.     

Weingarten surfaces and nonlinear partial differential equations

The sine-Gordon equation has been known for a long time as the equation satisfied by the angle between the two asymptotic lines on a surface inR ³ with constant Gauss curvature –1. In this paper, we consider the following question: Does any other soliton equation have a similar geometric interpretation? A method for finding all the equations that have such an interpretation using Weingarten surfaces inR ³ is given. It is proved that the sine-Gordon equation is the only partial differential equation describing a class of Weingarten surfaces inR ³ and having a geometricso(3)-scattering system. Moreover, it is shown that the elliptic Liouville equation and the elliptic sinh-Gordon equation are the only partial differential equations describing classes of Weingarten surfaces inR ³ and having geometricso(3,C)-scattering systems.     

Convergence of non-ergodic dynamical systems

Summary Let {T _t} be a flow on a probability space (S,L,}) which describes the time evolution of a dynamical system with state space S, and interpret as the initial distribution of the system. Then the distribution of the system at time t is given by T _t ^–1 . Our aim is to study the asymptotic behavior of T _t ^–1 both in general and in the particular cases of random rate and almost periodic systems. The results seem to indicate that convergence or mean convergence is the normal behavior in the non-ergodic case.     

A convergence theory of multilevel additive Schwarz methods on unstructured meshes

We develop a convergence theory for two level and multilevel additive Schwarz domain decomposition methods for elliptic and parabolic problems on general unstructured meshes in two and three dimensions. The coarse and fine grids are assumed only to be shape regular, and the domains formed by the coarse and fine grids need not be identical. In this general setting, our convergence theory leads to completely local bounds for the condition numbers of two level additive Schwarz methods, which imply that these condition numbers are optimal, or independent of fine and coarse mesh sizes and subdomain sizes if the overlap amount of a subdomain with its neighbors varies proportionally to the subdomain size. In particular, we will show that additive Schwarz algorithms are still very efficient for nonselfadjoint parabolic problems with only symmetric, positive definite solvers both for local subproblems and for the global coarse problem. These conclusions for elliptic and parabolic problems improve our earlier results in [12, 15, 16]. Finally, the convergence theory is applied to multilevel additive Schwarz algorithms. Under some very weak assumptions on the fine mesh and coarser meshes, e.g., no requirements on the relation between neighboring coarse level meshes, we are able to derive a condition number bound of the orderO(² L ²), where = max₁lL(h _l +_l– 1)/ _l,h _l is the element size of thelth level mesh, _l the overlap of subdomains on thelth level mesh, andL the number of mesh levels.The work was partially supported by the NSF under contract ASC 92-01266, and ONR under contract ONR-N00014-92-J-1890. The second author was also partially supported by HKRGC grants no. CUHK 316/94E and the Direct Grant of CUHK.     

Integer points on hypersurfaces

Very general hypersurfaces in ⁴ contain r ^2+(4/9) integer points in any ball of radiusr>1. As a consequence, an irreducible algebraic hypersurface in ⁿ (wheren4) which is not a cylinder and is of degreed, contains c(d, n)r ^{n–1–(5/9)} integer points in a ball of radiusr. This improves on the known boundc(d, n)r ^n–(3/2).Meinem verehrten Lehrer Professor E. Hlawka zum siebzigsten Geburtstag gewidmetWritten with partial support from NSF-MCS-8211461.     

Optimization of the Hermitian and Skew-Hermitian Splitting Iteration for Saddle-Point Problems

We study the asymptotic rate of convergence of the alternating Hermitian/skew-Hermitian iteration for solving saddle-point problems arising in the discretization of elliptic partial differential equations. By a careful analysis of the iterative scheme at the continuous level we determine optimal convergence parameters for the model problem of the Poisson equation written in div-grad form. We show that the optimized convergence rate for small mesh parameter h is asymptotically 1–O(h ^1/2). Furthermore we show that when the splitting is used as a preconditioner for a Krylov method, a different optimization leading to two clusters in the spectrum gives an optimal, h-independent, convergence rate. The theoretical analysis is supported by numerical experiments.This revised version was published online in October 2005 with corrections to the Cover Date.