Search

This paper is concerned with the convergence properties of iterative algorithms of conjugate gradient type applied to the computation of an extreme eigenvalue of a Hermitian operator via the optimization of the Rayleigh quotient functional. The algorithms in focus employ the line search for the extremum of the Rayleigh quotient functional in the direction that is a linear combination of the gradient and the previous search direction. An asymptotically explicit equation for the reduction in the eigenvalue error after the line search step as a function of the search direction is derived and applied to the analysis of the local convergence properties (i.e., the error reduction after an iteration) of the algorithms in question. The local (stepwise) asymptotic equivalence of various conjugate gradient algorithms and the generalized Davidson method is proved, and a new convergence estimate for conjugate gradient iterations is derived, showing the reduction in the eigenvalue error after any two consecutive iterations. The paper's analysis extensively employs remarkable properties of the operator of the so-called Jacobi orthogonal complement correction equation. [ABSTRACT FROM AUTHOR]

In this paper we consider the numerical solution of discrete boundary integral equations on polyhedral surfaces in three dimensions. When the solution contains typical edge singularities, highly stretched meshes are preferred to uniform meshes, since they reduce the number of degrees of freedom needed to obtain a fixed accuracy. The classical panel-clustering method can still be applied in the presence of such highly stretched meshes. However, we will show that the savings in computation time and storage become suboptimal because the nearfield matrix arising in the panel-clustering algorithm is no longer as sparse as it is in the case of uniform meshes. Hence, a natural question arises as to whether a new enhanced panel-clustering algorithm can be designed which performs efficiently even in the presence of highly stretched meshes. The main result of this paper is to formulate such an enhanced version of the panel-clustering algorithm. The key features of the algorithm are (i) the employment of partial analytic integration in the direction of stretching, yielding a new kernel function on a one-dimensional manifold where the influence of high aspect ratios in the stretched elements is removed, and (ii) the introduction of a generalized admissibility condition with respect to the partially integrated kernel, which ensures that certain stretched clusters which are inadmissible in the classical sense now become admissible. In the context of a model problem, we prove that our algorithm yields an accurate (up to the discretization error) matrix-vector multiplication which requires ...(NlogκN) operations, where N is the number of degrees of freedom and k is small and independent of the aspect ratio. The generalized admissibility condition can be viewed as an addition to the classical method which may be useful in general when stretched meshes are present. We also have performed a numerical experiment which shows that the sparsity of the nearfield matrix for the enhanced panel-clustering method is not negatively affected by stretched elements, and the method will perform optimally. [ABSTRACT FROM AUTHOR]

In this paper, a new space-time discretization is proposed which is based on a modified mass matrix. The mass associated with a surface layer of elements is redistributed such that the inertia at the boundary is removed. This approach is motivated by the observation that standard space-time discretization schemes applied to dynamic contact problems yield spurious oscillations. A widely used approach for the numerical simulation of these problems is based on Lagrange multipliers which represent the contact stresses. But the algebraic contact conditions in combination with the inertia volume terms often yield nonphysical results for the contact stresses, and the stability of the algorithm can be lost. Our modified matrix is calculated via nonstandard quadrature formulas that require no extra computational effort. In addition, the conservation properties of the underlying algorithm are carried over to the modified method, and the standard optimal a priori estimates are still satisfied. Numerical examples confirm the optimality of the approach and its stabilization effect applied to contact problems. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of testing whether a large matrix X has a prescribed structure by looking at the magnitude of a displacement matrix D(X) associated with the structure. We provide parameters on the basis of which one can judge whether the problem is well-conditioned or ill-conditioned. It turns out that even for very general structures it is the minimal eigenvalues of positive definite and banded Toeplitz matrices that are the most important of these parameters. [ABSTRACT FROM AUTHOR]

The mortar methods are based on domain decomposition and they allow for the coupling of different variational approximations in different subdomains. The resulting methods are nonconforming but still yield optimal approximations. In this paper, we will discuss iterative substructuring algorithms for the algebraic systems arising from the discretization of symmetric, second-order, elliptic equations in two dimensions. Both spectral and finite element methods, for geometrically conforming as well as nonconforming domain decompositions, are studied. In each case, we obtain a polylogarithmic bound on the condition number of the preconditioned matrix. [ABSTRACT FROM AUTHOR]

Spline collocation differentiation matrices arising when solving PDEs with periodic boundary conditions have block circulant structure. In this paper, we use this fact to present an eigenvalue analysis for a large class of such spline collocation differentiation matrices. We use this to discuss the stability of collocation algorithms for parabolic and hyperbolic problems and fast collocation algorithms for elliptic PDEs. [ABSTRACT FROM AUTHOR]

We derive two reformulations of the C¹ Hermite subdivision scheme introduced by Merrien. One where we separate computation of values and derivatives and one based of refinement of a control polygon. We show that the latter leads to a subdivision matrix which is totally positive. Based on this we give algorithms for constructing subdivision curves that preserve positivity, monotonicity, and convexity. [ABSTRACT FROM AUTHOR]

A new version of the fast multipole method (FMM) for the evaluation of potential fields on the line is introduced. It uses a new representation of potential fields, based on generalized Gaussian quadratures [J. Ma, V. Rokhlin, and S. Wandzura, SIAM J. Numer. Anal., 33 (1996), pp. 971­996; N. Yarvin and V. Rokhlin, SIAM J. Sci. Comput., 20 (1999), pp. 699­718]. In this representation, most translation operators are diagonal. To efficiently incorporate this representation into the FMM, an apparatus is introduced for transforming between different types of expansions. This apparatus is highly general and is based on formulae for the least squares approximation of linear operators. The performance of the method is illustrated with several numerical examples; it is roughly twice as fast as previously published algorithms. [ABSTRACT FROM AUTHOR]

An iterative method is proposed to solve the Schrödinger eigenvalue problem in a wavelet framework. Orthonormal wavelets are used to represent the corresponding operator as a sparse band matrix. This representation, called the nonstandard (NS) form, is obtained by means of the Beylkin­Coifman­Rokhlin (BCR) algorithm and simplifies the numerical calculations. Problems due to the one-dimensional mathematical model and to the discretization process receive special attention. [ABSTRACT FROM AUTHOR]