Componentwise error analysis for FFTs with applications to fast Helmholtz solvers

We analyze the stability of the Cooley-Tukey algorithm for the Fast Fourier Transform of ordern=2 ^k and of its inverse by using componentwise error analysis.We prove that the components of the roundoff errors are linearly related to the result in exact arithmetic. We describe the structure of the error matrix and we give optimal bounds for the total error in infinity norm and inL ₂ norm.The theoretical upper bounds are based on a worst case analysis where all the rounding errors work in the same direction. We show by means of a statistical error analysis that in realistic cases the max-norm error grows asymptotically like the logarithm of the sequence length by machine precision.Finally, we use the previous results for introducing tight upper bounds on the algorithmic error for some of the classical fast Helmholtz equation solvers based on the Faster Fourier Transform and for some algorithms used in the study of turbulence.     

A Posteriori Error Estimators of Gradient Recovery Type for Elliptic Obstacle Problems

In this paper, we present a posteriori error estimates of gradient recovery type for elliptic obstacle problems. The a posteriori error estimates provide both lower and upper error bounds. It is shown to be equivalent to the discretization error in an energy type norm for general meshes. Furthermore, when the solution is smooth and the mesh is uniform, it is shown to be asymptotically exact. Some numerical results which demonstrate the theoretical results are also reported in this paper.     

Estimates of the <Emphasis Type="Italic">l</Emphasis><Subscript>2</Subscript> norm of the error in the conjugate gradient algorithm

In this paper we derive a formula relating the norm of the l₂ error to the A-norm of the error in the conjugate gradient algorithm. Approximating the different terms in this formula, we obtain an estimate of the l₂ norm during the conjugate gradient iterations. Numerical experiments are given for several matrices. AMS subject classification 65F10, 65G20     

A posteriori error estimates of stabilized finite volume method for the Stokes equations

In this work, the residual‐type posteriori error estimates of stabilized finite volume method are studied for the steady Stokes problem based on two local Gauss integrations. By using the residuals between the source term and numerical solutions, the computable global upper and local lower bounds for the errors of velocity in H¹ norm and pressure in L² norm are derived. Furthermore, a global upper bound of u ? u_h in L²‐norm is also derived. Finally, some numerical experiments are provided to verify the performances of the established error estimators. Copyright © 2015 John Wiley & Sons, Ltd.     

A posteriori error estimates of constrained optimal control problem governed by convection diffusion equations

In this paper, we study a posteriori error estimates of the edge stabilization Galerkin method for the constrained optimal control problem governed by convection-dominated diffusion equations. The residual-type a posteriori error estimators yield both upper and lower bounds for control u measured in L ²-norm and for state y and costate p measured in energy norm. Two numerical examples are presented to illustrate the effectiveness of the error estimators provided in this paper.      

Numerical experiments in computing bounds for the norm of the error in the preconditioned conjugate gradient algorithm

In this paper we consider algorithms to compute bounds of the A-norm of the error in the preconditioned conjugate gradient (PCG) algorithm. We extend to PCG formulas that were given in an earlier paper [8]. We give numerical experiments which show that good upper and lower bounds can be obtained provided estimates of the lowest and largest eigenvalues of the preconditioned matrix are given or adaptively computed. This revised version was published online in August 2006 with corrections to the Cover Date.     

On the Randomized Error of Polynomial Methods for Eigenvector and Eigenvalue Estimates

In this paper we consider the problem of estimating the largest eigenvalue and the corresponding eigenvector of a symmetric matrix. In particular, we consider iterative methods, such as the power method and the Lanczos method. These methods need a starting vector which is usually chosen randomly. We analyze the behavior of these methods when the initial vector is chosen with uniform distribution over the unitn-dimensional sphere. We extend and generalize the results reported earlier. In particular, we give upper and lower bounds on the _pnorm of the randomized error, and we improve previously known bounds with a detailed analysis of the role of the multiplicity of the largest eigenvalue.     

New results on the convergence of the conjugate gradient method

This paper is concerned with proving theoretical results related to the convergence of the conjugate gradient (CG) method for solving positive definite symmetric linear systems. Considering the inverse of the projection of the inverse of the matrix, new relations for ratios of the A‐norm of the error and the norm of the residual are provided, starting from some earlier results of Sadok (Numer. Algorithms 2005; 40 :201–216). The proofs of our results rely on the well‐known correspondence between the CG method and the Lanczos algorithm. Copyright © 2008 John Wiley & Sons, Ltd.     

Class of tight bounds on the Q‐function with closed‐form upper bound on relative error

In this paper, we propose a novel class of parametric bounds on the Q‐function, which are lower bounds for 1 ≤ a < 3 and x > x_t = (a (a‐1) / (3‐a))^1/2, and upper bound for a = 3. We prove that the lower and upper bounds on the Q‐function can have the same analytical form that is asymptotically equal, which is a unique feature of our class of tight bounds. For the novel class of bounds and for each particular bound from this class, we derive the beneficial closed‐form expression for the upper bound on the relative error. By comparing the bound tightness for moderate and large argument values not only numerically, but also analytically, we demonstrate that our bounds are tighter compared with the previously reported bounds of similar analytical form complexity.     

Estimates of the deviations from the exact solutions for variational inequalities describing the stationary flow of certain viscous incompressible fluids

This paper is concerned with computable and guaranteed upper bounds of the difference between exact solutions of variational inequalities arising in the theory of viscous fluids and arbitrary approximations in the corresponding energy space. Such estimates (also called error majorants of functional type) have been derived for the considered class of nonlinear boundary‐value problems in (Math. Meth. Appl. Sci. 2006; 29:2225–2244) with the help of variational methods based on duality theory from convex analysis. In the present paper, it is shown that error majorants can be derived in a different way by certain transformations of the variational inequalities that define generalized solutions. The error bounds derived by this techniques for the velocity function differ from those obtained by the variational method. These estimates involve only global constants coming from Korn‐ and Friedrichs‐type inequalities, which are not difficult to evaluate in case of Dirichlet boundary conditions. For the case of mixed boundary conditions, we also derive another form of the estimate that contains only one constant coming from the following assertion: the L² norm of a vector‐valued function from H¹(Ω) in the factor space generated by the equivalence with respect to rigid motions is bounded by the L² norm of the symmetric part of the gradient tensor. As for some ‘simple’ domains such as squares or cubes, the constants in this inequality can be found analytically (or numerically), we obtain a unified form of an error majorant for any domain that admits a decomposition into such subdomains. Copyright © 2009 John Wiley & Sons, Ltd.     

Generalized Christoffel functions and error of positive quadrature

The author gives some upper and lower bounds for the generalized Christoffel functions related to a Ditzian-Totik generalized weight. As an application, an error estimate of Gauss quadrature formula inL ₁-weighted norm is derived.Dedicated to Prof. Luigi Gatteschi on the occasion of his 70th birthdayWork sponsored by MURST 40%.     

Multigrid methods for the symmetric interior penalty method on graded meshes

The symmetric interior penalty (SIP) method on graded meshes and its fast solution by multigrid methods are studied in this paper. We obtain quasi‐optimal error estimates in both the energy norm and the L₂ norm for the SIP method, and prove uniform convergence of the W‐cycle multigrid algorithm for the resulting discrete problem. The performance of these methods is illustrated by numerical results. Copyright © 2009 John Wiley & Sons, Ltd.     

A posteriori error estimates for elliptic problems with Dirac delta source terms

The aim of this paper is to introduce residual type a posteriori error estimators for a Poisson problem with a Dirac delta source term, in L ^p norm and W^1,p seminorm. The estimators are proved to yield global upper and local lower bounds for the corresponding norms of the error. They are used to guide adaptive procedures, which are experimentally shown to lead to optimal orders of convergence.     

Fast enclosure for the minimum norm least squares solution of the matrix equation AXB = C

Fast algorithms for enclosing the minimum norm least squares solution of the matrix equation AXB = C are proposed. To develop these algorithms, theories for obtaining error bounds of numerical solutions are established. The error bounds obtained by these algorithms are verified in the sense that all the possible rounding errors have been taken into account. Techniques for accelerating the enclosure and obtaining smaller error bounds are introduced. Numerical results show the properties of the proposed algorithms. Copyright © 2015 John Wiley & Sons, Ltd.     

Vizing's coloring algorithm and the fan number

Most upper bounds for the chromatic index of a graph come from algorithms that produce edge colorings. One such algorithm was invented by Vizing [Diskret Analiz 3 (1964), 25–30] in 1964. Vizing's algorithm colors the edges of a graph one at a time and never uses more than Δ+µ colors, where Δ is the maximum degree and µ is the maximum multiplicity, respectively. In general, though, this upper bound of Δ+µ is rather generous. In this paper, we define a new parameter fan(G) in terms of the degrees and the multiplicities of G. We call fan(G) the fan number of G. First we show that the fan number can be computed by a polynomial‐time algorithm. Then we prove that the parameter Fan(G)=max{Δ(G), fan(G)} is an upper bound for the chromatic index that can be realized by Vizing's coloring algorithm. Many of the known upper bounds for the chromatic index are also upper bounds for the fan number. Furthermore, we discuss the following question. What is the best (efficiently realizable) upper bound for the chromatic index in terms of Δ and µ ? Goldberg's Conjecture supports the conjecture that χ′+1 is the best efficiently realizable upper bound for χ′ at all provided that P ≠ NP . © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 115–138, 2010     

The rate of convergence of an approximate matrix factorization semi-direct method

Summary The definition of acceleration parameters for the convergence of a sparseLU factorization semi-direct method is shown to be based on lower and upper bounds of the extreme eigevalues of the iteration matrix. Optimum values of these parameters are established when the eigenvalues of the iteration matrix are either real or complex. Estimates for the computational work required to reduce theL ₂ norm of the error by a specified factor are also given.     

The Role of the Inner Product in Stopping Criteria for Conjugate Gradient Iterations

Two natural and efficient stopping criteria are derived for conjugate gradient (CG) methods, based on iteration parameters. The derivation makes use of the inner product matrix B-defining the CG method. In particular, the relationship between the eigenvalues and B-norm of a matrix is investigated, and it is shown that the ratio of largest to smallest eigenvalues defines the B-condition number of the matrix. Upper and lower bounds on various measures of the error are also given. The compound stopping criterion presented here is an obvious default in software packages because it does not require any additional norm computations.     

Improvement of the formal and numerical estimation of the constant in some Markov-Bernstein inequalities

Some methods of numerical analysis, used for obtaining estimations of zeros of polynomials, are studied again, more especially in the case where the zeros of these polynomials are all strictly positive, distinct and real. They give, in particular, formal lower and upper bounds for the smallest zero. Thanks to them, we produce new formal lower and upper bounds of the constant in Markov-Bernstein inequalities in L ² for the norm corresponding to the Laguerre and Gegenbauer inner products. In fact, since this constant is the inverse of the square root of the smallest zero of a polynomial, we give formal lower and upper bounds of this zero. Moreover, a new sufficient condition is given in order that a polynomial has some complex zeros. This revised version was published online in June 2006 with corrections to the Cover Date.     

Quasi-norm a priori and a posteriori error estimates for the nonconforming approximation of p-Laplacian

Summary. In this paper, we derive quasi-norm a priori and a posteriori error estimates for the Crouzeix-Raviart type finite element approximation of the p-Laplacian. Sharper a priori upper error bounds are obtained. For instance, for sufficiently regular solutions we prove optimal a priori error bounds on the discretization error in an energy norm when . We also show that the new a posteriori error estimates provide improved upper and lower bounds on the discretization error. For sufficiently regular solutions, the a posteriori error estimates are further shown to be equivalent on the discretization error in a quasi-norm. Received January 25, 1999 / Revised version received June 5, 2000 Published online March 20, 2001     

A primal‐dual method for the Meyer model of cartoon and texture decomposition

In this paper, we study the original Meyer model of cartoon and texture decomposition in image processing. The model, which is a minimization problem, contains an l₁‐based TV‐norm and an l_∞‐based G‐norm. The main idea of this paper is to use the dual formulation to represent both TV‐norm and G‐norm. The resulting minimization problem of the Meyer model can be given as a minimax problem. A first‐order primal‐dual algorithm can be developed to compute the saddle point of the minimax problem. The convergence of the proposed algorithm is theoretically shown. Numerical results are presented to show that the original Meyer model can decompose better cartoon and texture components than the other testing methods.