Trigonometric Hermite wavelet approximation for the integral equations of second kind with weakly singular kernel

This paper is concerned with a trigonometric Hermite wavelet Galerkin method for the Fredholm integral equations with weakly singular kernel. The kernel function of this integral equation considered here includes two parts, a weakly singular kernel part and a smooth kernel part. The approximation estimates for the weakly singular kernel function and the smooth part based on the trigonometric Hermite wavelet constructed by E. Quak [Trigonometric wavelets for Hermite interpolation, Math. Comp. 65 (1996) 683–722] are developed. The use of trigonometric Hermite interpolant wavelets for the discretization leads to a circulant block diagonal symmetrical system matrix. It is shown that we only need to compute and store O(N)$\mathrm{O}(N)$ entries for the weakly singular kernel representation matrix with dimensions N²$N^2$ which can reduce the whole computational cost and storage expense. The computational schemes of the resulting matrix elements are provided for the weakly singular kernel function. Furthermore, the convergence analysis is developed for the trigonometric wavelet method in this paper.     

Singular integral transforms and fast numerical algorithms

Fast algorithms for the accurate evaluation of some singular integral operators that arise in the context of solving certain partial differential equations within the unit circle in the complex plane are presented. These algorithms are generalizations and extensions of a fast algorithm of Daripa [11]. They are based on some recursive relations in Fourier space and the FFT (Fast Fourier Transform), and have theoretical computational complexity of the order O(N) per point, where N² is the total number of grid points. An application of these algorithms to quasiconformal mappings of doubly connected domains onto annuli is presented in a follow-up paper.     

Optimal adaptive solution of initial-value problems with unknown singularities

The optimal solution of initial-value problems in ODEs is well studied for smooth right-hand side functions. Much less is known about the optimality of algorithms for singular problems. In this paper, we study the (worst case) solution of scalar problems with a right-hand side function having r   continuous bounded derivatives in R$\mathbf{R}$, except for an unknown singular point. We establish the minimal worst case error for such problems (which depends on r similarly as in the smooth case), and define optimal adaptive algorithms. The crucial point is locating an unknown singularity of the solution by properly adapting the grid. We also study lower bounds on the error of an algorithm for classes of singular problems. In the case of a single singularity with nonadaptive information, or in the case of two or more singularities, the error of any algorithm is shown to be independent of r.     

Preconditionings and splittings for rectangular systems

Summary Recently Eiermann, Marek, and Niethammer have shown how to applysemiiterative methods to a fixed point systemx=Tx+c which isinconsistent or in whichthe powers of the fixed point operator T have no limit, to obtain iterative methods which converge to some approximate solution to the fixed point system. In view of their results we consider here stipulations on apreconditioning QAx=Qb of the systemAx=b and, separately, on asplitting A=M–N which lead to fixed point systems such that, with the aid of a semiiterative method, the iterative scheme converges to a weighted Moore-Penrose solution to the systemAx=b. We show in several ways that to obtain a meaningful limit point from a semiiterative method requires less restrictions on the splittings or the reconditionings than those which have been required in the classical Picard iterative method (see, e.g., the works of Berman and Plemmons, Berman and Neumann, and Tanabe).We pay special attention to the case when the weighted Moore-Penrose solution which is sought is the minimal norm least squares solution toAx=b.Research supported by the Deutsche ForschungsgemeinschaftPartially supported by AFOSR research grant 88-0047     

Parallel algorithms for variational inequalities over the Cartesian product of the intersections of the fixed point sets of nonexpansive mappings

This paper presents a framework of iterative algorithms for the variational inequality problem over the Cartesian product of the intersections of the fixed point sets of nonexpansive mappings in real Hilbert spaces. Strong convergence theorems are established under a certain contraction assumption with respect to the weighted maximum norm. The proposed framework produces as a simplest example the hybrid steepest descent method, which has been developed for solving the monotone variational inequality problem over the intersection of the fixed point sets of nonexpansive mappings. An application to a generalized power control problem and numerical examples are demonstrated.     

On the convergence of splittings for semidefinite linear systems

Recently, Lee et al. [Young-ju Lee, Jinbiao Wu, Jinchao Xu, Ludmil Zikatanov, On the convergence of iterative methods for semidefinite linear systems, SIAM J. Matrix Anal. Appl. 28 (2006) 634-641] introduce new criteria for the semi-convergence of general iterative methods for semidefinite linear systems based on matrix splitting. The new conditions generalize the classical notion of P-regularity introduced by Keller [H.B. Keller, On the solution of singular and semidefinite linear systems by iterations, SIAM J. Numer. Anal. 2 (1965) 281-290]. In view of their results, we consider here stipulations on a splitting A=M-N, which lead to fixed point systems such that, the iterative scheme converges to a weighted Moore-Penrose solution to the system Ax=b. Our results extend the result of Lee et al. to a more general case and we also show that it requires less restrictions on the splittings than Keller’s P-regularity condition to ensure the convergence of iterative scheme.     

Algorithmes parallèles asynchrones pour des systèmes singuliers

In this paper we give a convergence result concerning parallel bounded delayed asynchronous algorithms for linear fixed point problems with nonexpansive linear mappings with respect to a weighted maximum norm. This allows us to propose parallel algorithms which converge to the solution of consistent singular systems, including singular M-matrices (see for more details [3]). An important characteristic of our technical framework is that we are able to describe two-stage algorithms.     

A note on properties of splittings of singular symmetric positive semidefinite matrices

Summary. Recently, Benzi and Szyld have published an important paper [1] concerning the existence and uniqueness of splittings for singular matrices. However, the assertion in Theorem 3.9 on the inheriting property of P-regular splitting for singular symmetric positive semidefinite matrices seems to be incorrect. As a complement of paper [1], in this short note we point out that if a matrix T is resulted from a P-regular splitting of a symmetric positive semidefinite matrix A, then splittings induced by T are not all P-regular. Received January 7, 1999 / Published online December 19, 2000     

Iterative algorithms for generalized mixed equilibrium problems

In this paper, we consider a generalized mixed equilibrium problem in real Hilbert space. Using the auxiliary principle, we define a class of resolvent mappings. Further, using fixed point and resolvent methods, we give some iterative algorithms for solving generalized mixed equilibrium problem. Furthermore, we prove that the sequences generated by iterative algorithms converge weakly to the solution of generalized mixed equilibrium problem. These results require monotonicity (θ-pseudo monotonicity) and continuity (Lipschitz continuity) for mappings.     

Scaled total least squares fundamentals

Summary. The standard approaches to solving overdetermined linear systems construct minimal corrections to the vector c and/or the matrix B such that the corrected system is compatible. In ordinary least squares (LS) the correction is restricted to c, while in data least squares (DLS) it is restricted to B. In scaled total least squares (STLS) [22], corrections to both c and B are allowed, and their relative sizes depend on a real positive parameter . STLS unifies several formulations since it becomes total least squares (TLS) when , and in the limit corresponds to LS when , and DLS when . This paper analyzes a particularly useful formulation of the STLS problem. The analysis is based on a new assumption that guarantees existence and uniqueness of meaningful STLS solutions for all parameters . It makes the whole STLS theory consistent. Our theory reveals the necessary and sufficient condition for preserving the smallest singular value of a matrix while appending (or deleting) a column. This condition represents a basic matrix theory result for updating the singular value decomposition, as well as the rank-one modification of the Hermitian eigenproblem. The paper allows complex data, and the equivalences in the limit of STLS with DLS and LS are proven for such data. It is shown how any linear system can be reduced to a minimally dimensioned core system satisfying our assumption. Consequently, our theory and algorithms can be applied to fully general systems. The basics of practical algorithms for both the STLS and DLS problems are indicated for either dense or large sparse systems. Our assumption and its consequences are compared with earlier approaches. Received June 2, 1999 / Revised version received July 3, 2000 / Published online July 25, 2001     

A class of polynomial variable metric algorithms for linear optimization

In the paper, the behaviour of interior point algorithms is analyzed by using a variable metric method approach. A class of polynomial variable metric algorithms is given achieving O ((n/β)L) iterations for solving a canonical form linear optimization problem with respect to a wide class of Riemannian metrics, wheren is the number of dimensions and β a fixed value. It is shown that the vector fields of several interior point algorithms for linear optimization is the negative Riemannian gradient vector field of a linear a potential or a logarithmic barrier function for suitable Riemannian metrics. Research Partially supported by the Hungarian National Research Foundation, Grant Nos. OTKA-T016413 and OTKA-2116.     

Least-squares fitting of circles and ellipses

Fitting circles and ellipses to given points in the plane is a problem that arises in many application areas, e.g., computer graphics, coordinate meteorology, petroleum engineering, statistics. In the past, algorithms have been given which fit circles and ellipses insome least-squares sense without minimizing the geometric distance to the given points.In this paper we present several algorithms which compute the ellipse for which thesum of the squares of the distances to the given points is minimal. These algorithms are compared with classical simple and iterative methods.Circles and ellipses may be represented algebraically, i.e., by an equation of the formF(x)=0. If a point is on the curve, then its coordinates x are a zero of the functionF. Alternatively, curves may be represented in parametric form, which is well suited for minimizing the sum of the squares of the distances.Dedicated to Åke Björck on the occasion of his 60th birthday     

Smallest singular value of a random rectangular matrix

We prove an optimal estimate of the smallest singular value of a random sub‐Gaussian matrix, valid for all dimensions. For an N × n matrix A with independent and identically distributed sub‐Gaussian entries, the smallest singular value of A is at least of the order √N ? √n ? 1 with high probability. A sharp estimate on the probability is also obtained. © 2009 Wiley Periodicals, Inc.     

Additive Schwarz algorithms for the p version of the Galerkin boundary element method

Summary. We study some additive Schwarz algorithms for the version Galerkin boundary element method applied to some weakly singular and hypersingular integral equations of the first kind. Both non-overlapping and overlapping methods are considered. We prove that the condition numbers of the additive Schwarz operators grow at most as independently of h, where p is the degree of the polynomials used in the Galerkin boundary element schemes and h is the mesh size. Thus we show that additive Schwarz methods, which were originally designed for finite element discretisation of differential equations, are also efficient preconditioners for some boundary integral operators, which are non-local operators. Received June 15, 1997 / Revised version received July 7, 1998 / Published online February 17, 2000     

Automatic solution of regular and singular vector Sturm-Liouville problems

This paper describes the algorithms and theory behind a new code for vector Sturm-Liouville problems. A new spectral function is defined for vector Sturm-Liouville problems; this is an integer valued function of the eigenparameter which has discontinuities precisely at the eigenvalues. We describe numerical algorithms which may be used to compute the new spectral function, and its use as amiss-distance function in a new code which solves automatically a large class of regular and singular vector Sturm-Liouville problems. Vector Sturm-Liouville problems arise naturally in quantum mechanical applications. Usually they are singular. The advantages of the author's code lie in its ability to solve singular problems automatically, and in the fact that the user may specify the required eigenvalue by its index.     

Regularity properties of free discontinuity sets

This paper is concerned with the problem of estimating the dimension, expected to be N−2, of the singular set of a minimizer of a functional with free discontinuities in N dimensions. The best result already known, namely the (N−1)-negligibility, is improved here.     

Finite element superconvergence approximation for one‐dimensional singularly perturbed problems

Superconvergence approximations of singularly perturbed two‐point boundary value problems of reaction‐diffusion type and convection‐diffusion type are studied. By applying the standard finite element method of any fixed order p on a modified Shishkin mesh, superconvergence error bounds of (N^?1 ln (N + 1))^p+1 in a discrete energy norm in approximating problems with the exponential type boundary layers are established. The error bounds are uniformly valid with respect to the singular perturbation parameter. Numerical tests indicate that the error estimates are sharp; in particular, the logarithmic factor is not removable. © 2002 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 18: 374–395, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/num.10001     

Low discrepancy sequences in high dimensions: How well are their projections distributed?

Quasi-Monte Carlo (QMC) methods have been successfully used to compute high-dimensional integrals arising in many applications, especially in finance. To understand the success and the potential limitation of QMC, this paper focuses on quality measures of point sets in high dimensions. We introduce the order-?$?$, superposition and truncation discrepancies, which measure the quality of selected projections of a point set on lower-dimensional spaces. These measures are more informative than the classical ones. We study their relationships with the integration errors and study the tractability issues. We present efficient algorithms to compute these discrepancies and perform computational investigations to compare the performance of the Sobol’ nets with that of the sets of Latin hypercube sampling and random points. Numerical results show that in high dimensions the superiority of the Sobol’ nets mainly derives from the one-dimensional projections and the projections associated with the earlier dimensions; for order-2 and higher-order projections all these point sets have similar behavior (on the average). In weighted cases with fast decaying weights, the Sobol’ nets have a better performance than the other two point sets. The investigation enables us to better understand the properties of QMC and throws new light on when and why QMC can have a better (or no better) performance than Monte Carlo for multivariate integration in high dimensions.     

Some vector sequence transformations with applications to systems of equations

First, recursive algorithms for implementing some vector sequence transformations are given. In a particular case, these transformations are generalizations of Shanks transformation and the G-transformation. When the sequence of vectors under transformation is generated by linear fixed point iterations, Lanczos' method and the CGS are recovered respectively. In the case of a sequence generated by nonlinear fixed point iterations, a quadratically convergent method based on the -algorithm is recovered and a nonlinear analog of the CGS method is obtained.