Wavelet sparse approximate inverse preconditioners

We show how to use wavelet compression ideas to improve the performance of approximate inverse preconditioners. Our main idea is to first transform the inverse of the coefficient matrix into a wavelet basis, before applying standard approximate inverse techniques. In this process, smoothness in the entries ofA ⁻¹ are converted into small wavelet coefficients, thus allowing a more efficient approximate inverse approximation. We shall justify theoretically and numerically that our approach is effective for matrices with smooth inverses. Supported by grants from ONR: ONR-N00014-92-J-1890, and the Army Research Office: DAAL-03-91-C-0047 (Univ. of Tenn. subcontract ORA4466.04 Amendment 1 and 2). The first and the third author also acknowledge support from RIACS/NASA Ames NAS 2-96027 and the Alfred P. Sloan Foundation as Doctoral Dissertation Fellows, respectively. the work was supported by the Natural Sciences and Engineering Research Council of Canada, the Information Technology Research Centre (which is funded by the Province of Ontario), and RIACS/NASA Ames NAS 2-96027.     

Computation of orthonormal factors for fundamental solution matrices

Summary. In this work, we introduce and analyze two new techniques for obtaining the Q factor in the QR factorization of some (or all) columns of a fundamental solution matrix Y of a linear differential system. These techniques are based on elementary Householder and Givens transformations. We implement and compare these new techniques with existing approaches on some examples. Received October 27, 1997 / Revised version received September 21, 1998 / Published online August 19, 1999     

A posteriori parameter choice strategies for some Newton type methods for the regularization of nonlinearill-posed problems

This paper treats a class of Newton type methods for the approximate solution of nonlinear ill-posed operator equations, that use so-called filter functions for regularizing the linearized equation in each Newton step. For noisy data we derive an aposteriori stopping rule that yields convergence of the iterates to asolution, as the noise level goes to zero, under certain smoothness conditions on the nonlinear operator. Appropriate closeness and smoothness assumptions on the starting value and the solution are shown to lead to optimal convergence rates. Moreover we present an application of the Newton type methods under consideration to a parameter identification problem, together with some numerical results. Received November 29, 1996 / Revised version received April 25, 1997     

Outer inverses and multi body system simulation

In this paper, a numerical method for solving overdetermined differential algebraic equations that arise in multi body dynamics is proposed. The method is based on Newton type iterations using outer inverses. We prove that the ssf method and tangent space parametrization can be regarded as particular cases of our method     

Diagonally compensated reduction and related preconditioning methods

When solving linear algebraic equations with large and sparse coefficient matrices, arising, for instance, from the discretization of partial differential equations, it is quite common to use preconditioning to accelerate the convergence of a basic iterative scheme. Incomplete factorizations and sparse approximate inverses can provide efficient preconditioning methods but their existence and convergence theory is based mostly on M-matrices (H-matrices). In some application areas, however, the arising coefficient matrices are not H-matrices. This is the case, for instance, when higher-order finite element approximations are used, which is typical for structural mechanics problems. We show that modification of a symmetric, positive definite matrix by reduction of positive offdiagonal entries and diagonal compensation of them leads to an M-matrix. This diagonally compensated reduction can take place in the whole matrix or only at the current pivot block in a recursive incomplete factorization method. Applications for constructing preconditioning matrices for finite element matrices are described.     

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.     

Convergence of Newton-like methods for singular operator equations using outer inverses

Summary We present a (semilocal) Kantorovich-type analysis for Newton-like methods for singular operator equations using outer inverses. We establish sharp generalizations of the Kantorovich theory and the Mysovskii theory for operator equations when the derivative is not necessarily invertible. The results reduce in the case of an invertible derivative to well-known theorems of Kantorovich and Mysovskii with no additional assumptions, unlike earlier theorems which impose strong conditions. The strategy of the analysis is based on Banach-type lemmas and perturbation bounds for outer inverses which show that the set of outer inverses (to a given bounded linear operator) admits selections that behave like bounded linear inverses, in contrast to inner inverses or generalized inverses which do not depend continuously on perturbations of the operator. We give two examples to illustrate our results and compare them with earlier results, and another numerical example to relate our results to computational issues.The research of the first author was partially supported by the National Science Foundation under grant DMS-901526. The research of the second author was supported by an Australian Research Council grant     

Fast transforms for tridiagonal linear equations

In this paper we study the use of the Fourier, Sine and Cosine Transform for solving or preconditioning linear systems, which arise from the discretization of elliptic problems. Recently, R. Chan and T. Chan considered circulant matrices for solving such systems. Instead of using circulant matrices, which are based on the Fourier Transform, we apply the Fourier and the Sine Transform directly. It is shown that tridiagonal matrices arising from the discretization of an onedimensional elliptic PDE are connected with circulant matrices by congruence transformations with the Fourier or the Sine matrix. Therefore, we can solve such linear systems directly, using only Fast Fourier Transforms and the Sherman-Morrison-Woodbury formula. The Fast Fourier Transform is highly parallelizable, and thus such an algorithm is interesting on a parallel computer. Moreover, similar relations hold between block tridiagonal matrices and Block Toeplitz-plus-Hankel matrices of ordern ²×n ² in the 2D case. This can be used to define in some sense natural approximations to the given matrix which lead to preconditioners for solving such linear systems.     

Solving some optimal control problems using the barrier penalty function method

In this paper we present a new approach to solve a two-level optimization problem arising from an approximation by means of the finite element method of optimal control problems governed by unilateral boundary-value problems. The problem considered is to find a minimum of a functional with respect to the control variablesu. The minimized functional depends on control variables and state variablesx. The latter are the optimal solution of an auxiliary quadratic programming problem, whose parameters depend onu.Our main idea is to replace this QP problem by its dual and then apply the barrier penalty method to this dual QP problem or to the primal one if it is in an appropriate form. As a result we obtain a problem approximating the original one. Its good property is the differentiable dependence of state variables with respect to the control variables. Furthermore, we propose a method for finding an approximate solution of a penalized lower-level problem if the optimal solution of the original QP problem is known. We apply the result obtained to some optimal shape design problems governed by the Dirichlet-Signorini boundary-value problem.This research was supported by the Academy of Finland and the Systems Research Institute of the Polish Academy of Sciences.     

Convergence of certain incomplete block factorization splittings

This note fills a logical gap in the theory of incomplete block factorizations of the generalized SSOR type. Namely, it is shown that using the so-called factorized sparse approximate inverses it is possible to preserve the symmetry of a given Stieltjes or positive definite H-matrix A in its incomplete block factorization K and to insure simultaneously the convergence of the related splitting A=K−R. Bibliography: 3 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 219, 1994, pp. 42–52. Translated by L. Yu. Kolotilina.     

Finite element approximation of viscoelastic fluid flow: Existence of approximate solutions and error bounds

Summary We study a finite element approximation of viscoelastic fluid flow obeying an Oldroyd B type constitutive law. The approximate stress, velocity and pressure are respectivelyP ₁ discontinuous,P ₂ continuous,P ₁ continuous. We use the method of Lesaint-Raviart for the convection of the extra stress tensor. We suppose that the continuous problem admits a sufficiently smooth and sufficiently small solution. We show by a fixed point method that the approximate problem has a solution and we give an error bound.This work has been supported in part by the GDR CNRS 901 Rhéologie der polymères fondus.     

Valuing Asian options using the finite element method and duality techniques

The main objective of this paper is to develop an adaptive finite element method for computation of the values, and different sensitivity measures, of the Asian option with both fixed and floating strike. The pricing is based on Black–Scholes PDE-model and a method developed by Ve?e? where the resulting PDEs are of parabolic type in one spatial dimension and can be applied to both continuous and discrete Asian options. We propose using an adaptive finite element method which is based on a posteriori estimates of the error in desired quantities, which we derive using duality techniques. The a posteriori error estimates are tested and verified, and are used to calculate optimal meshes for each type of option. The use of adapted meshes gives superior accuracy and performance with less degrees of freedom than using uniform meshes. The suggested adaptive finite element method is stable, gives fast and accurate results, and can be applied to other types of options as well.     

Generalized block Lanczos methods for large unsymmetric eigenproblems

Generalized block Lanczos methods for large unsymmetric eigenproblems are presented, which contain the block Arnoldi method, and the block Arnoldi algorithms are developed. The convergence of this class of methods is analyzed when the matrix A is diagonalizable. Upper bounds for the distances between normalized eigenvectors and a block Krylov subspace are derived, and a priori theoretical error bounds for Ritz elements are established. Compared with generalized Lanczos methods, which contain Arnoldi's method, the convergence analysis shows that the block versions have two advantages: First, they may be efficient for computing clustered eigenvalues; second, they are able to solve multiple eigenproblems. However, a deep analysis exposes that the approximate eigenvectors or Ritz vectors obtained by general orthogonal projection methods including generalized block methods may fail to converge theoretically for a general unsymmetric matrix A even if corresponding approximate eigenvalues or Ritz values do, since the convergence of Ritz vectors needs more sufficient conditions, which may be impossible to satisfy theoretically, than that of Ritz values does. The issues of how to restart and to solve multiple eigenproblems are addressed, and some numerical examples are reported to confirm the theoretical analysis. Received July 7, 1994 / Revised version received March 1, 1997     

Algebraic multilevel preconditioning methods. I

Summary A recursive way of constructing preconditioning matrices for the stiffness matrix in the discretization of selfadjoint second order elliptic boundary value problems is proposed. It is based on a sequence of nested finite element spaces with the usual nodal basis functions. Using a nodeordering corresponding to the nested meshes, the finite element stiffness matrix is recursively split up into two-level block structures and is factored approximately in such a way that any successive Schur complement is replaced (approximated) by a matrix defined recursively and thereform only implicitely given. To solve a system with this matrix we need to perform a fixed number (v) of iterations on the preceding level using as an iteration matrix the preconditioning matrix already defined on that level. It is shown that by a proper choice of iteration parameters it suffices to use \left( {1 - \gamma ^2 } \right)^{ - \tfrac{1}{2}} $$ " align="middle" border="0"> iterations for the so constructedv-foldV-cycle (wherev=2 corresponds to aW-cycle) preconditioning matrices to be spectrally equivalent to the stiffness matrix. The conditions involve only the constant in the strengthened C.-B.-S. inequality for the corresponding two-level hierarchical basis function spaces and are therefore independent of the regularity of the solution for instance. If we use successive uniform refinements of the meshes the method is of optimal order of computational complexity, if . Under reasonable assumptions of the finite element mesh, the condition numbers turn out to be so small that there are in practice few reasons to use an accelerated iterative method like the conjugate gradient method, for instance.Dedicated to the memory of Peter HenriciThe research of the second author reported here was supported in part by the Committee of Science, Bulgaria, under Grant No. 55/26.03.87     

Riccati-based preconditioner for computing invariant subspaces of large matrices

Summary. This paper introduces and analyzes the convergence properties of a method that computes an approximation to the invariant subspace associated with a group of eigenvalues of a large not necessarily diagonalizable matrix. The method belongs to the family of projection type methods. At each step, it refines the approximate invariant subspace using a linearized Riccati's equation which turns out to be the block analogue of the correction used in the Jacobi-Davidson method. The analysis conducted in this paper shows that the method converges at a rate quasi-quadratic provided that the approximate invariant subspace is close to the exact one. The implementation of the method based on multigrid techniques is also discussed and numerical experiments are reported. Received June 15, 2000 / Revised version received January 22, 2001 / Published online October 17, 2001     

A convergence analysis for a sweeping preconditioner for block tridiagonal systems of linear equations

We study sweeping preconditioners for symmetric and positive definite block tridiagonal systems of linear equations. The algorithm provides an approximate inverse that can be used directly or in a preconditioned iterative scheme. These algorithms are based on replacing the Schur complements appearing in a block Gaussian elimination direct solve by hierarchical matrix approximations with reduced off‐diagonal ranks. This involves developing low rank hierarchical approximations to inverses. We first provide a convergence analysis for the algorithm for reduced rank hierarchical inverse approximation. These results are then used to prove convergence and preconditioning estimates for the resulting sweeping preconditioner. Copyright © 2014 John Wiley & Sons, Ltd.     

Third order nonoscillatory central scheme for hyperbolic conservation laws

Summary. A third-order accurate Godunov-type scheme for the approximate solution of hyperbolic systems of conservation laws is presented. Its two main ingredients include: 1. A non-oscillatory piecewise-quadratic reconstruction of pointvalues from their given cell averages; and 2. A central differencing based on staggered evolution of the reconstructed cell averages. This results in a third-order central scheme, an extension along the lines of the second-order central scheme of Nessyahu and Tadmor \cite{NT}. The scalar scheme is non-oscillatory (and hence – convergent), in the sense that it does not increase the number of initial extrema (– as does the exact entropy solution operator). Extension to systems is carried out by componentwise application of the scalar framework. In particular, we have the advantage that, unlike upwind schemes, no (approximate) Riemann solvers, field-by-field characteristic decompositions, etc., are required. Numerical experiments confirm the high-resolution content of the proposed scheme. Thus, a considerable amount of simplicity and robustness is gained while retaining the expected third-order resolution. Received April 10, 1996 / Revised version received January 20, 1997     

Incremental unknowns for solving partial differential equations

Summary Incremental unknowns have been proposed in [T] as a method to approximate fractal attractors by using finite difference approximations of evolution equations. In the case of linear elliptic problems, the utilization of incremental unknown methods provides a new way for solving such problems using several levels of discretization; the method is similar but different from the classical multigrid method.In this article we describe the application of incremental unknowns for solving Laplace equations in dimensions one and two. We provide theoretical results concerning two-level approximations and we report on numerical tests done with multi-level approximations.     

Error estimates for a mixed finite volume method for the p-Laplacian problem

In this work we propose and analyze a mixed finite volume method for the p-Laplacian problem which is based on the lowest order Raviart–Thomas element for the vector variable and the P1 nonconforming element for the scalar variable. It is shown that this method can be reduced to a P1 nonconforming finite element method for the scalar variable only. One can then recover the vector approximation from the computed scalar approximation in a virtually cost-free manner. Optimal a priori error estimates are proved for both approximations by the quasi-norm techniques. We also derive an implicit error estimator of Bank–Weiser type which is based on the local Neumann problems.This work was supported by the Post-doctoral Fellowship Program of Korea Science & Engineering Foundation (KOSEF).     

Some exponentially decreasing error bounds for a numerical inversion of the Laplace transform

Convergence properties of a class of least-squares methods for finding approximate inverses of the Laplace transform are obtained by using reproducing kernel Hilbert space techniques (or, alternatively, related minimization techniques) and some classical interpolation results.