A domain decomposition discretization of parabolic problems

In recent years, domain decomposition methods have attracted much attention due to their successful application to many elliptic and parabolic problems. Domain decomposition methods treat problems based on a domain substructuring, which is attractive for parallel computation, due to the independence among the subdomains. In principle, domain decomposition methods may be applied to the system resulting from a standard discretization of the parabolic problems or, directly, be carried out through a discretization of parabolic problems. In this paper, a direct domain decomposition method is introduced to discretize the parabolic problems. The stability and convergence of this algorithm are analyzed. This work was supported in part by Polish Sciences Foundation under grant 2P03A00524. This work was supported in part by the US Department of Energy under Contracts DE-FG02-92ER25127 and by the Director, Office of Science, Advanced Scientific Computing Research, U.S. Department of Energy under contract DE-AC02-05CH11231.     

Subspace-restricted singular value decompositions for linear discrete ill-posed problems

The truncated singular value decomposition is a popular solution method for linear discrete ill-posed problems. These problems are numerically underdetermined. Therefore, it can be beneficial to incorporate information about the desired solution into the solution process. This paper describes a modification of the singular value decomposition that permits a specified linear subspace to be contained in the solution subspace for all truncations. Modifications that allow the range to contain a specified subspace, or that allow both the solution subspace and the range to contain specified subspaces also are described.     

Rate of Convergence for some constraint decomposition methods for nonlinear variational inequalities

Summary. Some general subspace correction algorithms are proposed for a convex optimization problem over a convex constraint subset. One of the nontrivial applications of the algorithms is the solving of some obstacle problems by multilevel domain decomposition and multigrid methods. For domain decomposition and multigrid methods, the rate of convergence for the algorithms for obstacle problems is of the same order as the rate of convergence for jump coefficient linear elliptic problems. In order to analyse the convergence rate, we need to decompose a finite element function into a sum of functions from the subspaces and also satisfying some constraints. A special nonlinear interpolation operator is introduced for decomposing the functions. Received December 13, 2001 / Revised version received February 19, 2002 / Published online June 17, 2002 This work was partially supported by the Norwegian Research Council under projects 128224/431 and SEP-115837/431.     

Evaluation of ST preconditioners for saddle point problems

The general block ST decomposition of the saddle point problem is used as a preconditioner to transform the saddle point problem into an equivalent symmetric and positive definite system. Such a decomposition is called a block ST preconditioner. Two general block ST preconditioners are proposed for saddle point problems with symmetric and positive definite (1,1)-block. Some estimations of the condition number of the preconditioned system are given. The same study is done for singular (1,1)-block.     

Parallel domain decomposition procedures of improved D-D type for parabolic problems

Two parallel domain decomposition procedures for solving initial-boundary value problems of parabolic partial differential equations are proposed. One is the extended D-D type algorithm, which extends the explicit/implicit conservative Galerkin domain decomposition procedures, given in [5], from a rectangle domain and its decomposition that consisted of a stripe of sub-rectangles into a general domain and its general decomposition with a net-like structure. An almost optimal error estimate, without the factor H^−1/2 given in Dawson-Dupont’s error estimate, is proved. Another is the parallel domain decomposition algorithm of improved D-D type, in which an additional term is introduced to produce an approximation of an optimal error accuracy in L²-norm.     

Domain decomposition method and elastic multi-structures: The stiffened plate problem

Summary Domain decomposition methods allow faster solution of partial differential equations in many cases. The efficiency of these methods mainly depends on the variables and operators chosen for the coupling between the subdomains; it is the preconditioning problem. In the modeling of multistructures, the partial differential equations have some specific properties that must be taken into account in a domain decomposition method. Different kinds of elliptic problems modeling stiffened plates in linearized elasticity are compared. One of them is remarkable as far as domain decomposition is concerned, since it is possible to associate particularly efficient preconditioner. A theoretical estimate for the conditioning is given, which is confirmed by several numerical experiments.     

Modifying the generalized singular value decomposition with application with application in direction-of-arrival finding

We consider updating and downdating problems for the generalized singular value decomposition (GSVD) of matrix pairs when new rows are added to one of the matrices or old rows are deleted. Two classes of algorithms are developed, one based on the CS decomposition formulation of the GSVD and the other based on the generalized eigenvalue decomposition formulation. In both cases we show that the updating and downdating problems can be reduced to a rank-one SVD updating problem. We also provide perturbation analysis for the cases when the added or deleted rows are subject to errors. Numerical experiments on direction-of-arrival (DOA) finding with colored noises are carried out to demonstrate the tracking ability of the algorithms. The work of the first author was supported in part by NSF grants CCR-9308399 and CCR-9619452. The work of the second author was supported in part by China State Major Key Project for Basic Researches.     

Multilevel iterative methods for mixed finite element discretizations of elliptic problems

Summary For solving second order elliptic problems discretized on a sequence of nested mixed finite element spaces nearly optimal iterative methods are proposed. The methods are within the general framework of the product (multiplicative) scheme for operators in a Hilbert space, proposed recently by Bramble, Pasciak, Wang, and Xu [5,6,26,27] and make use of certain multilevel decomposition of the corresponding spaces for the flux variable.     

A parallel iterative procedure applicable to the approximate solution of second order partial differential equations by mixed finite element methods

Summary A parallelizable interative procedure based on domain decomposition techniques is defined and analyzed for mixed finite element methods for elliptic equations, with the analysis being presented for the decomposition of the domain into the individual elements associated with the mixed method or into larger subdomains. Applications to time-dependent problems are indicated.The research of Douglas was supported in part by the NSF and the AHPCRC and that of Paes Leme in part by the CNPq and the FINEP.     

Adaptive filtering

Summary. In this paper, the adaptive filtering method is introduced and analysed. This method leads to robust algorithms for the solution of systems of linear equations which arise from the discretisation of partial differential equations with strongly varying coefficients. These iterative algorithms are based on the tangential frequency filtering decompositions (TFFD). During the iteration with a preliminary preconditioner, the adaptive test vector method calculates new test vectors for the TFFD. The adaptive test vector iterative method allows the combination of the tangential frequency decomposition and other iterative methods such as multi-grid. The connection with the TFFD improves the robustness of these iterative methods with respect to varying coefficients. Interface problems as well as problems with stochastically distributed properties are considered. Realistic numerical experiments confirm the efficiency of the presented algorithms. Received June 26, 1996 / Revised version received October 7, 1996     

The truncatedSVD as a method for regularization

The truncated singular value decomposition (SVD) is considered as a method for regularization of ill-posed linear least squares problems. In particular, the truncated SVD solution is compared with the usual regularized solution. Necessary conditions are defined in which the two methods will yield similar results. This investigation suggests the truncated SVD as a favorable alternative to standard-form regularization in cases of ill-conditioned matrices with well-determined numerical rank.This work was carried out while the author visited the Dept. of Computer Science, Stanford University, California, U.S.A., and was supported in part by National Science Foundation Grant Number DCR 8412314, by a Fulbright Supplementary Grant, and by the Danish Space Board.     

Schwarz methods for inequalities with contraction operators

We prove the convergence of some multiplicative and additive Schwarz methods for inequalities which contain contraction operators. The problem is stated in a reflexive Banach space and it generalizes the well-known fixed-point problem in the Hilbert spaces. Error estimation theorems are given for three multiplicative algorithms and two additive algorithms. We show that these algorithms are in fact Schwarz methods if the subspaces are associated with a decomposition of the domain. Also, for the one- and two-level methods in the finite element spaces, we write the convergence rates as functions of the overlapping and mesh parameters. They are similar with the convergence rates of these methods for linear problems. Besides the direct use of the five algorithms for the inequalities with contraction operators, we can use the above results to obtain the convergence rate of the Schwarz method for other types of inequalities or nonlinear equations. In this way, we prove the convergence and estimate the error of the one- and two-level Schwarz methods for some inequalities in Hilbert spaces which are not of the variational type, and also, for the Navier–Stokes problem. Finally, we give conditions of existence and uniqueness of the solution for all problems we consider. We point out that these conditions and the convergence conditions of the proposed algorithms are of the same type.     

An algorithm using the finite volume element method and its splitting extrapolation

This paper is to present a new efficient algorithm by using the finite volume element method and its splitting extrapolation. This method combines the local conservation property of the finite volume element method and the advantages of splitting extrapolation, such as a high order of accuracy, a high degree of parallelism, less computational complexity and more flexibility than a Richardson extrapolation. Because the splitting extrapolation formulas only require us to solve a set of smaller discrete subproblems on different coarser grids in parallel instead of on the globally fine grid, a large scale multidimensional problem is turned into a set of smaller discrete subproblems. Additionally, this method is efficient for solving interface problems if we regard the interfaces of the problems as the interfaces of the initial domain decomposition.     

Modified ILU as a smoother

Summary. We study a variant of ILU, viz. with , as a smoother in multi-grid methods. The -decomposition is characterized by the fact that the rest matrix is not zero on the diagonal but instead of that satisfies . The use of as a smoother is recommended because of the observed robustness when it is applied to singular perturbation problems. However, until now, a proof of robustness has only been given for one model anisotropic equation by Wittum. In this paper, we show that the -decomposition of an M-matrix exists and yields a regular splitting. For symmetric M-matrices and symmetric decomposition ``patterns' we prove that the eigenvalues of the -smoother are in \footnote{After this paper was submitted, the author learned of a report of Notay (\cite{239.5}) where related results are discussed}, whereas the rest matrix is at most a modest factor larger than the rest matrix of the unmodified ILU-decomposition. With these properties, robustness can now be shown when the rest matrix of the unmodified decomposition is ``small enough'. Our results generalize Wittum's results for the model problem. Received August 16, 1992 / Revised version received September 7, 1993     

Quantitative stability analysis of optimal solutions in PDE-constrained optimization

PDE-constrained optimization problems under the influence of perturbation parameters are considered. A quantitative stability analysis for local optimal solutions is performed. The perturbation directions of greatest impact on an observed quantity are characterized using the singular value decomposition of a certain linear operator. An efficient numerical method is proposed to compute a partial singular value decomposition for discretized problems, with an emphasis on infinite-dimensional parameter and observation spaces. Numerical examples are provided.     

On the abstract theory of additive and multiplicative Schwarz algorithms

Summary. In recent years, it has been shown that many modern iterative algorithms (multigrid schemes, multilevel preconditioners, domain decomposition methods etc.) for solving problems resulting from the discretization of PDEs can be interpreted as additive (Jacobi-like) or multiplicative (Gauss-Seidel-like) subspace correction methods. The key to their analysis is the study of certain metric properties of the underlying splitting of the discretization space into a sum of subspaces and the splitting of the variational problem on into auxiliary problems on these subspaces. In this paper, we propose a modification of the abstract convergence theory of the additive and multiplicative Schwarz methods, that makes the relation to traditional iteration methods more explicit. The analysis of the additive and multiplicative Schwarz iterations can be carried out in almost the same spirit as in the traditional block-matrix situation, making convergence proofs of multilevel and domain decomposition methods clearer, or, at least, more classical. In addition, we present a new bound for the convergence rate of the appropriately scaled multiplicative Schwarz method directly in terms of the condition number of the corresponding additive Schwarz operator. These results may be viewed as an appendix to the recent surveys [X], [Ys]. Received February 1, 1994 / Revised version received August 1, 1994     

Nonlinear structural finite element analysis using the preconditioned Lanczos method on serial and parallel computers

The application of the Lanczos algorithm in Newton-like methods for solving non-linear systems of equations arising in nonlinear structural finite element analysis is presented. It is shown that with appropriate preconditioners iterative methods can be developed which are robust and efficient even for ill conditioned problems. Though the real advantage of iterative solvers seems to exist on distributed memory machines, even on serial machines the performance can be improved compared with direct solvers while saving memory capacity. With a specific modification of the Lanczos algorithm in combination with arc-length procedures a further speed-up of the nonlinear analysis can be achieved. For parallel implementations domain decomposition methods are used. A parallel preconditioning strategy based on an incomplete factorisation method is presented. An example is taken and the quality and efficiency of two different domain decomposition methods are discussed for a large shell structure. This work was supported by the BMBF (Bundesministerium für Bildung und Forschung) of Germany.     

The product-product singular value decomposition of matrix triplets

A new decomposition of a matrix triplet (A, B, C) corresponding to the singular value decomposition of the matrix productABC is developed in this paper, which will be termed theProduct-Product Singular Value Decomposition (PPSVD). An orthogonal variant of the decomposition which is more suitable for the purpose of numerical computation is also proposed. Some geometric and algebraic issues of the PPSVD, such as the variational and geometric interpretations, and uniqueness properties are discussed. A numerical algorithm for stably computing the PPSVD is given based on the implicit Kogbetliantz technique. A numerical example is outlined to demonstrate the accuracy of the proposed algorithm.The work was partially supported by NSF grant DCR-8412314.     

Nonstandard coarse spaces and Schwarz methods for elliptic problems with discontinuous coefficients using non-conforming elements

Summary. Two-level domain decomposition methods are developed for a simple nonconforming approximation of second order elliptic problems. A bound is established for the condition number of these iterative methods, that grows only logarithmically with the number of degrees of freedom in each subregion. This bound holds for two and three dimensions and is independent of jumps in the value of the coefficients and number of subregions. We introduce face coarse spaces, and isomorphisms to map between conforming and nonconforming spaces. ReceivedMarch 1, 1995 / Revised version received January 16, 1996     

Numerical methods for finding multiple eigenvalues of matrices depending on parameters

Summary. Let be a square matrix dependent on parameters and , of which we choose as the eigenvalue parameter. Many computational problems are equivalent to finding a point such that has a multiple eigenvalue at . An incomplete decomposition of a matrix dependent on several parameters is proposed. Based on the developed theory two new algorithms are presented for computing multiple eigenvalues of with geometric multiplicity . A third algorithm is designed for the computation of multiple eigenvalues with geometric multiplicity but which also appears to have local quadratic convergence to semi-simple eigenvalues. Convergence analyses of these methods are given. Several numerical examples are presented which illustrate the behaviour and applications of our methods. Received December 19, 1994 / Revised version received January 18, 1996