Algebraic multigrid methods for Laplacians of graphs

Classical algebraic multigrid theory relies on the fact that the system matrix is positive definite. We extend this theory to cover the positive semidefinite case as well, by formulating semiconvergence results for these singular systems. For the class of irreducible diagonal dominant singular M-matrices we show that the requirements of the developed theory hold and that the coarse level systems are still of the same class, if the C/F-splitting is good enough. An important example for matrices that are irreducible diagonal dominant M-matrices are Laplacians of graphs. Recent shape optimizing methods for graph partitioning require to solve singular linear systems involving these Laplacians. We present convergence results as well as experimental results for numerous graphs arising from finite element discretizations with up to 10⁶ vertices.     

Asymptotics of regularized solutions of a linear nonautonomous system of advanced differential equations

For a nonautonomous system of linear advanced differential equations, we find asymptotic formulas analytically determining how the regular solutions of this system on an interval of the positive half-line depend on the admissible error. The problem is solved in the following setting: additional smoothness conditions are imposed on the initial functions, but the boundary conditions providing a continuous extension of the solutions of the Cauchy problem to an interval of the positive half-line are violated.     

Improved Hessian approximation with modified secant equations for symmetric rank-one method

Symmetric rank-one (SR1) is one of the competitive formulas among the quasi-Newton (QN) methods. In this paper, we propose some modified SR1 updates based on the modified secant equations, which use both gradient and function information. Furthermore, to avoid the loss of positive definiteness and zero denominators of the new SR1 updates, we apply a restart procedure to this update. Three new algorithms are given to improve the Hessian approximation with modified secant equations for the SR1 method. Numerical results show that the proposed algorithms are very encouraging and the advantage of the proposed algorithms over the standard SR1 and BFGS updates is clearly observed.     

An analysis of bilinear transform polynomial methods of inversion of Laplace transforms

Summary. Methods for the numerical inversion of a Laplace transform which use a special bilinear transformation of are particularly effective in many cases and are widely used. The main purpose of this paper is to analyze the convergence and conditioning properties of a special class of such methods, characterized by the use of Lagrange interpolation. The results derived apply both to complex and real inversion, and show that some known inversion methods are in fact in this class. Received June 21, 1993 / Revised version received March 10, 1994     

Sylvester Tikhonov-regularization methods in image restoration

In this paper, we consider large-scale linear discrete ill-posed problems where the right-hand side contains noise. Regularization techniques such as Tikhonov regularization are needed to control the effect of the noise on the solution. In many applications such as in image restoration the coefficient matrix is given as a Kronecker product of two matrices and then Tikhonov regularization problem leads to the generalized Sylvester matrix equation. For large-scale problems, we use the global-GMRES method which is an orthogonal projection method onto a matrix Krylov subspace. We present some theoretical results and give numerical tests in image restoration.     

More on the weeks method for the numerical inversion of the Laplace transform

Summary Most of the numerical methods for the inversion of the Laplace Transform require the values of several incidental parameters. Generally, these parameters are related to the properties of the algorithm and to the analytical properties of the Laplace Transform functionF(s).One of the most promising inversion methods, the Weeks methods, computes the inverse functionf(t) as a series expansion of Laguerre functions involving two parameters, usually denoted by andb. In this paper we characterize the optimal choiceb _opt ofb, which maximizes the rate of convergence of the series, in terms of the location of the singularities ofF(s).     

Quadrature formulas for oscillatory integral transforms

Summary Quadrature formulas are obtained for the Fourier and Bessel transforms which correspond to the well-known Gauss-Laguerre formula for the Laplace transform. These formulas provide effective asymptotic approximations, complete with error bounds. Comparison is also made between the quadrature formulas and the asymptotic expansions of these transforms.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada under Contract A7359     

A modified Newton–Lavrentiev regularization for nonlinear ill-posed Hammerstein-type operator equations

Recently, a new iterative method, called Newton–Lavrentiev regularization (NLR) method, was considered by George (2006) for regularizing a nonlinear ill-posed Hammerstein-type operator equation in Hilbert spaces. In this paper we introduce a modified form of the NLR method and derive order optimal error bounds by choosing the regularization parameter according to the adaptive scheme considered by Pereverzev and Schock (2005).     

A class of function spaces and its application in solving second-order nonlinear differential equations

In this paper, we prove an existence theorem for time global monotone positive solutions of nonlinear second-order ordinary differential equations by applying the Schauder-Tikhonov fixed point theorem. This result generalizes the result of existence on a half-line given in Yin (2003) [8].     

Maximum entropy reconstruction using derivative information part 2: computational results

Summary. Maximum entropy density estimation, a technique for reconstructing an unknown density function on the basis of certain measurements, has applications in various areas of applied physical sciences and engineering. Here we present numerical results for the maximum entropy inversion program based on a new class of information measures which are designed to control derivative values of the unknown densities. Received January 3, 1994 / Revised version received May 25, 1994     

Interpolatory product quadratures for Cauchy principal value integrals with Freud weights

Summary. We prove convergence results and error estimates for interpolatory product quadrature formulas for Cauchy principal value integrals on the real line with Freud–type weight functions. The formulas are based on polynomial interpolation at the zeros of orthogonal polynomials associated with the weight function under consideration. As a by–product, we obtain new bounds for the derivative of the functions of the second kind for these weight functions. Received July 15, 1997 / Revised version received August 25, 1998     

A “multigrid” extension of theFFT for the numerical inversion of Fourier and Laplace Transforms

An algorithm for accurate numerical inversion of slowly convergent Fourier and Laplace Transforms is studied. It makes use of several equidistant grids with the same number of points, covering different symmetric intervals of the time and frequency axes. Typically, the number of operations per computed function value is about twice as large as for an ordinary FFT. The distribution of points is, however, for many applications much more adequate because, globally, the union of the grids is an approximately equidistant point set on a logarithmic scale.Dedicated to Gene H. Golub on the occasion of his 60'th birthday     

On quadrature methods for the double layer potential equation over the boundary of a polyhedron

Summary In this paper we consider a quadrature method for the solution of the double layer potential equation corresponding to Laplace's equation in a threedimensional polyhedron. We prove the stability for our method in case of special triangulations over the boundary of the polyhedron. The assumptions imposed on the triangulations are analogous to those appearing in the one-dimensional case. Finally, we establish the rates of convergence and discuss the effect of mesh refinement near the corners and edges of the polyhedron.     

Sparse potentials with fractional Hausdorff dimension

We construct non-random bounded discrete half-line Schrödinger operators which have purely singular continuous spectral measures with fractional Hausdorff dimension (in some interval of energies). To do this we use suitable sparse potentials. Our results also apply to whole line operators, as well as to certain random operators. In the latter case we prove and compute an exact dimension of the spectral measures.     

Incomplete data problems in x-ray computerized tomography

Summary The reconstruction of an object from its x-ray scans is achieved by the inverse Radon transform of the measured data. For fast algorithms and stable inversion the directions of the x rays have to be equally distributed. In the present paper we study the intrinsic problems arising when the directions are restricted to a limited range by computing the singular value decomposition of the Radon transform for the limited angle problem. Stability considerations show that parts of the spectrum cannot be reconstructed and the irrecoverable functions are characterized.     

Multiple positive solutions for a class of integral inclusions

This paper deals with sufficient conditions for the existence of at least two positive solutions for a class of integral inclusions arising in the traffic theory. To show our main results, we apply a norm-type expansion and compression fixed point theorem for multivalued map due to Agarwal and O’Regan [A note on the existence of multiple fixed points for multivalued maps with applications, J. Differential Equation 160 (2000) 389–403].     

Extended product integration rules

In this paper we introduce a class of extended product quadrature rules to associate with the corresponding standard product rules, and present an algorithm for their construction. A general discussion on the convergence of such formulas is then given. Finally some examples and applications are considered.Work sponsored by the Ministero della Pubblica Istruzione of Italy.     

Diophantine Integral Geometry

In his works [1], [2] and [3], the author succeeded in establishing several inversion formulas for Radon transform on Euclidean space, Damek-Ricci space and also on a finite set. The present paper deals with Radon transform R on discrete hyperplanes in the lattice defined by linear diophantine equations. More precisely, we study carefully various natural questions in this context: specific properties of the discrete Radon transform R and its dual R*, inversion formula for R (see Theorem 4.1) and also an appropriate support theorem in the discrete case (see Theorem 5.3).      

Interval oscillation criteria for second order partial differential equations with delays

In this paper, we present new interval oscillation criteria related to integral averaging technique for second order partial differential equations with delays that are different from most known ones in the sense that they are based on the information only on a sequence of subintervals of [_t0,∞)$[t_0,\infty )$, rather than on whole half-line. Our results are sharper than some previous results and handles the cases which are not covered by known criteria.