The discrete picard condition for discrete ill-posed problems

We investigate the approximation properties of regularized solutions to discrete ill-posed least squares problems. A necessary condition for obtaining good regularized solutions is that the Fourier coefficients of the right-hand side, when expressed in terms of the generalized SVD associated with the regularization problem, on the average decay to zero faster than the generalized singular values. This is the discrete Picard condition. We illustrate the importance of this condition theoretically as well as experimentally.This work was carried out during a visit to Dept. of Mathematics, UCLA, and was supported by the Danish Natural Science Foundation, by the National Science Foundation under contract NSF-DMS87-14612, and by the Army Research Office under contract No. DAAL03-88-K-0085.     

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.     

Solving balanced Procrustes problem with some constraints by eigenvalue decomposition

The balanced Procrustes problem with some special constraints such as symmetric orthogonality and symmetric idempotence are considered. By one time eigenvalue decomposition of the matrix product generated by the matrices A and B, the constrained solutions are constructed simply. Similar strategy is applied to the problem with the corresponding P-commuting constraints with a given symmetric matrix P. Numerical examples are presented to show the efficiency of the proposed methods.     

Accelerated Landweber iterations for the solution of ill-posed equations

Summary In this paper, the potentials of so-calledlinear semiiterative methods are considered for the approximate solution of linear ill-posed problems and ill conditioned matrix equations. Several efficient two-step methods are presented, most of which have been introduced earlier in the literature. Stipulating certain conditions concerning the smoothness of the solution, a notion of optimal speed of convergence may be formulated. Various direct and converse results are derived to illustrate the properties of this concept.If the problem's right hand side data are contaminated by noise, semiiterative methods may be used asregularization methods. Assuming optimal rate of convergence of the iteration for the unperturbed problem, the regularized approximations will be of order optimal accuracy.To derive these results, specific properties of polynomials are used in connection with the basic theory of solving ill-posed problems. Rather recent results onfast decreasing polynomials are applied to answer an open question of Brakhage.Numerical examples are given including a comparison to the method of conjugate gradients.This research was sponsored by the Deutsche Forschungsgemeinschaft (DFG).     

Orthogonal polynomials and semi-iterative methods for the Drazin-inverse solution of singular linear systems

Summary. In this work we present a novel class of semi-iterative methods for the Drazin-inverse solution of singular linear systems, whether consistent or inconsistent. The matrices of these systems are allowed to have arbitrary index and arbitrary spectra in the complex plane. The methods we develop are based on orthogonal polynomials and can all be implemented by 4-term recursion relations independently of the index. We give all the computational details of the associated algorithms. We also give a complete convergence analysis for all methods. Received June 28, 2000 / Revised version received May 23, 2001 / Published online January 30, 2002     

A numerical study of optimized sparse preconditioners

Preconditioning strategies based on incomplete factorizations and polynomial approximations are studied through extensive numerical experiments. We are concerned with the question of the optimal rate of convergence that can be achieved for these classes of preconditioners.Our conclusion is that the well-known Modified Incomplete Cholesky factorization (MIC), cf. e.g., Gustafsson [20], and the polynomial preconditioning based on the Chebyshev polynomials, cf. Johnson, Micchelli and Paul [22], have optimal order of convergence as applied to matrix systems derived by discretization of the Poisson equation. Thus for the discrete two-dimensional Poisson equation withn unknowns,O(n ^1/4) andO(n ^1/2) seem to be the optimal rates of convergence for the Conjugate Gradient (CG) method using incomplete factorizations and polynomial preconditioners, respectively. The results obtained for polynomial preconditioners are in agreement with the basic theory of CG, which implies that such preconditioners can not lead to improvement of the asymptotic convergence rate.By optimizing the preconditioners with respect to certain criteria, we observe a reduction of the number of CG iterations, but the rates of convergence remain unchanged.Supported by The Norwegian Research Council for Science and the Humanities (NAVF) under grants no. 413.90/002 and 412.93/005.Supported by The Royal Norwegian Council for Scientific and Industrial Research (NTNF) through program no. STP.28402: Toolkits in industrial mathematics.     

On a new notion of the solution to an ill-posed problem

A new understanding of the notion of the stable solution to ill-posed problems is proposed. The new notion is more realistic than the old one and better fits the practical computational needs. A method for constructing stable solutions in the new sense is proposed and justified. The basic point is: in the traditional definition of the stable solution to an ill-posed problem Au=f, where A is a linear or nonlinear operator in a Hilbert space H, it is assumed that the noisy data {f_δ,δ} are given, ‖f−f_δ‖≤δ, and a stable solution u_δ:=R_δf_δ is defined by the relation lim_δ→0‖R_δf_δ−y‖=0, where y solves the equation Au=f, i.e., Ay=f. In this definition y and f are unknown. Any f∈B(f_δ,δ) can be the exact data, where B(f_δ,δ):={f:‖f−f_δ‖≤δ}.The new notion of the stable solution excludes the unknown y and f from the definition of the solution. The solution is defined only in terms of the noisy data, noise level, and an a priori information about a compactum to which the solution belongs.     

Some comparison theorems for nonnegative splittings of matrices

Summary In a recent paper the author has proposed some theorems on the comparison of the asymptotic rates of convergence of two nonnegative splittings. They extended the corresponding result of Miller and Neumann and implied the earlier theorems of Varga, Beauwens, Csordas and Varga. An open question by Miller and Neumann, which additional and appropriate conditions should be imposed to obtain strict inequality, was also answered. This article continues to investigate the comparison theorems for nonnegative splittings. The new results extend and imply the known theorems by the author, Miller and Neumann.The Project Supported by the Natural Science Foundation of Jiangsu Province Education Commission     

The effect of non-optimal bases on the convergence of Krylov subspace methods

Summary There are many examples where non-orthogonality of a basis for Krylov subspace methods arises naturally. These methods usually require less storage or computational effort per iteration than methods using an orthonormal basis (optimal methods), but the convergence may be delayed. Truncated Krylov subspace methods and other examples of non-optimal methods have been shown to converge in many situations, often with small delay, but not in others. We explore the question of what is the effect of having a non-optimal basis. We prove certain identities for the relative residual gap, i.e., the relative difference between the residuals of the optimal and non-optimal methods. These identities and related bounds provide insight into when the delay is small and convergence is achieved. Further understanding is gained by using a general theory of superlinear convergence recently developed. Our analysis confirms the observed fact that in exact arithmetic the orthogonality of the basis is not important, only the need to maintain linear independence is. Numerical examples illustrate our theoretical results.This revised version was published online in June 2005 due to a typesetting mistake in the footnote on page 7.     

Analysis and computation of a least-squares method for consistent mesh tying

In the finite element method, a standard approach to mesh tying is to apply Lagrange multipliers. If the interface is curved, however, discretization generally leads to adjoining surfaces that do not coincide spatially. Straightforward Lagrange multiplier methods lead to discrete formulations failing a first-order patch test [T.A. Laursen, M.W. Heinstein, Consistent mesh-tying methods for topologically distinct discretized surfaces in non-linear solid mechanics, Internat. J. Numer. Methods Eng. 57 (2003) 1197–1242].     

On the numerical condition of a generalized Hankel eigenvalue problem

The generalized eigenvalue problem with H a Hankel matrix and the corresponding shifted Hankel matrix occurs in number of applications such as the reconstruction of the shape of a polygon from its moments, the determination of abscissa of quadrature formulas, of poles of Padé approximants, or of the unknown powers of a sparse black box polynomial in computer algebra. In many of these applications, the entries of the Hankel matrix are only known up to a certain precision. We study the sensitivity of the nonlinear application mapping the vector of Hankel entries to its generalized eigenvalues. A basic tool in this study is a result on the condition number of Vandermonde matrices with not necessarily real abscissas which are possibly row-scaled. B. Beckermann was supported in part by INTAS research network NaCCA 03-51-6637. G. H. Golub was supported in part by DOE grant DE-FC-02-01ER41177. G. Labahn was supported in part by NSERC and MITACS Canada grants.     

A preconditioning approach to the pagerank computation problem

Some spectral properties of the transition matrix of an oriented graph indicate the preconditioning of Euler-Richardson (ER) iterative scheme as a good way to compute efficiently the vertexrank vector associated with such graph. We choose the preconditioner from an algebra U of matrices, thereby obtaining an ER_U method, and we observe that ER_U can outperform ER in terms of rate of convergence. The proposed preconditioner can be updated at a very low cost whenever the graph changes, as is the case when it represents a generic set of information. The particular U utilized requires a surplus of operations per step and memory allocations, which make ER_U superior to ER for not too wide graphs. However, the observed high improvement in convergence rate obtained by preconditioning and the general theory developed, are a reason for investigating different choices of U, more efficient for huge graphs.     

Deflated GMRES for systems with multiple shifts and multiple right-hand sides

We consider solution of multiply shifted systems of nonsymmetric linear equations, possibly also with multiple right-hand sides. First, for a single right-hand side, the matrix is shifted by several multiples of the identity. Such problems arise in a number of applications, including lattice quantum chromodynamics where the matrices are complex and non-Hermitian. Some Krylov iterative methods such as GMRES and BiCGStab have been used to solve multiply shifted systems for about the cost of solving just one system. Restarted GMRES can be improved by deflating eigenvalues for matrices that have a few small eigenvalues. We show that a particular deflated method, GMRES-DR, can be applied to multiply shifted systems.In quantum chromodynamics, it is common to have multiple right-hand sides with multiple shifts for each right-hand side. We develop a method that efficiently solves the multiple right-hand sides by using a deflated version of GMRES and yet keeps costs for all of the multiply shifted systems close to those for one shift. An example is given showing this can be extremely effective with a quantum chromodynamics matrix.     

Limiting accuracy of segregated solution methods for nonsymmetric saddle point problems

Nonsymmetric saddle point problems arise in a wide variety of applications in computational science and engineering. The aim of this paper is to discuss the numerical behavior of several nonsymmetric iterative methods applied for solving the saddle point systems via the Schur complement reduction or the null-space projection approach. Krylov subspace methods often produce the iterates which fluctuate rather strongly. Here we address the question whether large intermediate approximate solutions reduce the final accuracy of these two-level (inner–outer) iteration algorithms. We extend our previous analysis obtained for symmetric saddle point problems and distinguish between three mathematically equivalent back-substitution schemes which lead to a different numerical behavior when applied in finite precision arithmetic. Theoretical results are then illustrated on a simple model example.     

Efficient numerical solution of the generalized Dirichlet-Neumann map for linear elliptic PDEs in regular polygon domains

A new and novel approach for analyzing boundary value problems for linear and for integrable nonlinear PDEs was recently introduced. For linear elliptic PDEs, an important aspect of this approach is the characterization of a generalized Dirichlet-Neumann map: given the derivative of the solution along a direction of an arbitrary angle to the boundary, the derivative of the solution perpendicularly to this direction is computed without solving on the interior of the domain. For this computation, a collocation-type numerical method has been recently developed. Here, we study the collocation’s coefficient matrix properties. We prove that, for the Laplace’s equation on regular polygon domains with the same type of boundary conditions on each side, the collocation matrix is block circulant, independently of the choice of basis functions. This leads to the deployment of the FFT for the solution of the associated collocation linear system, yielding significant computational savings. Numerical experiments are included to demonstrate the efficiency of the whole computation.     

A solution to Dilworth's congruence lattice problem

We construct an algebraic distributive lattice D that is not isomorphic to the congruence lattice of any lattice. This solves a long-standing open problem, traditionally attributed to R.P. Dilworth, from the forties. The lattice D has a compact top element and ℵω+1 compact elements. Our results extend to any algebra possessing a congruence-compatible structure of a join-semilattice with a largest element.     

A convergence analysis of block accelerated over-relaxation iterative methods for weak block H-matrices to partition π

The aim of this paper is to establish the convergence of the block iteration methods such as the block successively accelerated over-relaxation method (BAOR) and the symmetric block successively accelerated over-relaxation method (BSAOR): Let be a weak block H-matrix to partition π, then for ,

     

On a class of matrices which arise in the numerical solution of Euler equations

Summary We study block matricesA=[A_ij], where every blockA _ij ^k,k is Hermitian andA _ii is positive definite. We call such a matrix a generalized H-matrix if its block comparison matrix is a generalized M-matrix. These matrices arise in the numerical solution of Euler equations in fluid flow computations and in the study of invariant tori of dynamical systems. We discuss properties of these matrices and we give some equivalent conditions for a matrix to be a generalized H-matrix.Research supported by the Graduiertenkolleg mathematik der Universität Bielefeld     

Analysis of a Stokes interface problem

We consider a stationary Stokes problem with a piecewise constant viscosity coefficient. For the variational formulation of this problem we prove a well-posedness result in which the constants are uniform with respect to the jump in the viscosity coefficient. We apply a standard discretization with a pair of LBB stable finite element spaces. The main result of the paper is an infsup result for the discrete problem that is uniform with respect to the jump in the viscosity coefficient. From this we derive a robust estimate for the discretization error. We prove that the mass matrix with respect to some suitable scalar product yields a robust preconditioner for the Schur complement. Results of numerical experiments are presented that illustrate this robustness property. This author was supported by the German Research Foundation through the guest program of SFB 540