Box-Splitting strategies for the interval Gauss-Seidel step in a global optimization method

We consider an algorithm for computing verified enclosures for all global minimizersx ^* and for the global minimum valuef ^*=f(x ^*) of a twice continuously differentiable functionf:? ⁿ →→ within a box [x]∈I→. Our algorithm incorporates the interval Gauss-Seidel step applied to the problem of finding the zeros of the gradient off. Here, we have to deal with the gaps produced by the extended interval division. It is possible to use different box-splitting strategies for handling these gaps, producing different numbers of subboxes. We present results concerning the impact of these strategies on the interval Gauss-Seidel step and therefore on our global optimization method. First, we give an overview of some of the techniques used in our algorithm, and we describe the modifications improving the efficiency of the interval Gauss-Seidel step by applying a special box-splitting strategy. Then, we have a look on special preconditioners for the Gauss-Seidel step, and we investigate the corresponding results for different splitting strategies. Test results for standard global optimization problems are discussed for different variants of our method in its portable PASCAL-XSC implementation. These results demonstrate that there are many cases in which the splitting strategy is more important for the efficiency of the algorithm than the use of preconditioners.     

A combined method for enclosing all solutions of nonlinear systems of polynomial equations

We consider the problem of finding interval enclosures of all zeros of a nonlinear system of polynomial equations. We present a method which combines the method of Gröbner bases (used as a preprocessing step), some techniques from interval analysis, and a special version of the algorithm of E. Hansen for solving nonlinear equations in one variable. The latter is applied to a triangular form of the system of equations, which is generated by the preprocessing step. Our method is able to check if the given system has a finite number of zeros and to compute verfied enclosures for all these zeros. Several test results demonstrate that our method is much faster than the application of Hansen’s multidimensional algorithm (or similar methods) to the original nonlinear systems of polynomial equations.     

A method for solving systems of linear interval equations applied to the Leontief input–output model of economics

A new approach to solving systems of linear interval equations based on the generalized procedure of interval extension is proposed. This procedure is based on the treatment of interval zero as an interval centered around zero, and for this reason it is called the “interval extended zero” method. Since the “interval extended zero” method provides a fuzzy solution to interval equations, its interval representations are proposed. It is shown that they may be naturally treated as modified operations of interval division. These operations are used for the modified interval extensions of known numerical methods for solving systems of linear equations and finally for solving systems of linear interval equations. Using a well known example, it is shown that the solution obtained by the proposed method can be treated as an inner interval approximation of the united solution and an outer interval approximation of the tolerable solution, and lies within the range of possible AE-solutions between the extreme tolerable and united solutions. Generally, we can say that the proposed method provides the results which can be treated as approximate formal solutions sometimes referred to as algebraic solutions. Seven known examples are used to illustrate the method’s efficacy and advantages in comparison with known methods providing formal (algebraic) solutions to systems of linear interval equations. It is shown that a new method provides results which are close to the so-called maximal inner solutions (the corresponding method was developed by Kupriyanova, Zyuzin and Markov) and the algebraic solutions obtained by the subdifferential Newton method proposed by Shary. It is important that the proposed method makes it possible to avoid inverted interval solutions. The influence of the system’s size and number of zero entries on the results is analyzed by applying the proposed method to the Leontief input–output model of economics.     

Analysis of validated error bounds of surface-to-surface intersection

In this paper, we address the problem of computing the error bounds of surface-to-surface intersection and propose a novel procedure to reduce them. We formulate the surface-to-surface intersection problem as solving a system of ordinary differential equations and using the validated ODE solver we compute the validated a priori enclosures of an intersection curve, in which the existence and the uniqueness of a solution are guaranteed. Then we use straight line enclosures to reduce the size of the a priori enclosures. These reduced enclosures are again enclosed by bounding curves, which can be used as the reduced error bounds of the intersection curve. We demonstrate our method with tangential and transversal intersections.     

Moving-window discrete Fourier transform

The moving-window discrete Fourier transform (MWDFT) is a dynamic spectrum analysis in which the next analysis interval differs from the previous one by including the next signal sample and excluding the first one from the previous analysis interval (Dillard in IEEE Trans Inform Theory 13:2–6, 1967, Comput Elect Eng 1:143–152, 1973, USA Patent 4023028, May 10, 1977). Such a spectrum analysis is necessary for time–frequency localization of analyzed signals with given peculiarities (Tolimieri and An in Time–frequency representations. Birkhauser, Basel, 1998). Using the well-known fast Fourier transform (FFT) towards this aim is not effective. Recursive algorithms which use only one complex multiplication for computing one spectrum sample during each analysis interval are more effective. The author improved one algorithm so that it is possible to use only one complex multiplication for computing two, four, and even eight (for complex signals) spectrum samples simultaneously. Problems of realization and application of the MWDFT are also considered in the paper.     

Certified meshing of Radial Basis Function based isosurfaces

Radial Basis Functions are widely used in scattered data interpolation. The surface-reconstruction method using radial basis functions consists of two steps: (i) computing an interpolating implicit function the zero set of which contains the points in the data set, followed by (ii) extraction of isocurves or isosurfaces. In this paper we focus on the second step, generalizing the work on certified meshing of implicit surfaces based on interval arithmetic (Plantinga and Vegter in Visual Comput. 23:45–58, 2007). It turns out that interval arithmetic, and even the usually faster affine arithmetic, are far too slow in the context of RBF-based implicit surface meshing. We present optimized strategies giving acceptable running times and better space complexity, exploiting special properties of RBF-interpolants. We present pictures and timing results confirming the improved quality of these optimized strategies.     

A Derivative-Free Algorithm for Computing Zeros of Analytic Functions

Let W be a simply connected region in , analytic in W and γ a positively oriented Jordan curve in W that does not pass through any zero of f. We present an algorithm for computing all the zeros of f that lie in the interior of γ. It proceeds by evaluating certain integrals along γ numerically and is based on the theory of formal orthogonal polynomials. The algorithm requires only f and not its first derivative f'. We have found that it gives accurate approximations for the zeros. Moreover, it is self-starting in the sense that it does not require initial approximations. The algorithm works for simple zeros as well as multiple zeros, although it is unable to compute the multiplicity of a zero explicitly. Numerical examples illustrate the effectiveness of our approach. Received: November 2, 1998; revised March 30, 1999     

A matrix nullspace approach for solving equality-constrained multivariable polynomial least-squares problems

We present an elimination theory-based method for solving equality-constrained multivariable polynomial least-squares problems in system identification. While most algorithms in elimination theory rely upon Groebner bases and symbolic multivariable polynomial division algorithms, we present an algorithm which is based on computing the nullspace of a large sparse matrix and the zeros of a scalar, univariate polynomial.     

Error Analysis of a Derivative-Free Algorithm for Computing Zeros of Holomorphic Functions

We consider the quadrature method developed by Kravanja and Van Barel (Computing 63(1):69–91, 1999) for computing all the zeros of a holomorphic function that lie inside the unit circle. The algorithm uses only the function values and no (first or higher order) derivatives. Information about the location of the zeros is obtained from certain integrals along the unit circle. In numerical computations these are replaced by their trapezoidal rule approximations. We investigate the resulting quadrature error. Our error analysis shows that the zeros located inside the unit circle do not affect the accuracy of the computed approximations whereas the quadrature error related to the zeros located outside the unit circle tends to zero exponentially as the number of quadrature points tends to infinity.     

Outer Estimation of Generalized Solution Sets to Interval Linear Systems

The work advances a numerical technique for computing enclosures of generalized AE-solution sets to interval linear systems of equations. We develop an approach (called algebraic) in which the outer estimation problem reduces to a problem of computing algebraic solutions of an auxiliary interval equation in Kaucher complete interval arithmetic.     

Über die Konvergenzordnung des Intervall-Newton-Verfahrens

It is well known that the classical Newton method is cubically convergent to a simple zero if the second derivative vanishes at the zero. We first show that this property does not hold for the interval-Newton-method. If, however, the interval arithmetic evaluation of the derivative in this method is replaced by the mean-value form or by the centered form, respectively, then the method is again cubically convergent.     

重节点埃尔米特插值算法与程序实现

研究了具有任意阶导数信息Hermite插值问题,使用广义差商的一种新的表示方法和构造广义差商表的一种新方法,给出具有任意阶导数信息Hermite插值算法和程序实现,拓展了牛顿差商插值公式和余项公式。     

Computation of the structural invariants of linear multivariable systems with an extended version of the program zeros

The structural invariants like finite and infinite zeros play an important role in many problems in the analysis of linear systems. In [1] Emami-Naeini and Van Dooren presented the program zeros for computing the finite zeros of a linear system, which in the author's opinion is at present the best commonly available program for this problem. Such a program does not exist for computing the other structural invariants, like the infinite zeros and the Kronecker indices. This paper presents an extended version of the program zeros, which computes the finite zeros as well as the other structural invariants.     

The root and Bell’s disk iteration methods are of the same error propagation characteristics in the simultaneous determination of the zeros of a polynomial,Part II: Round-off error analysis by use of interval arithmetic

In Part I (Ikhile, 2008) [4], it was established that the root and Bell’s disk/point iteration methods with or without correction term are of the same asymptotic error propagation characteristics in the simultaneous determination of the zeros of a polynomial. This concluding part of the investigation is a study in round-offs, its propagation and its effects on convergence employing interval arithmetic means. The purpose is to consequently draw attention on the effects of round-off errors introduced from the point arithmetic part, on the rate of convergence of the generalized root and Bell’s simultaneous interval iteration algorithms and its enhanced modifications introduced in Part I for the numerical inclusion of all the zeros of a polynomial simultaneously. The motivation for studying the effects of round-off error propagation comes from the fact that the readily available computing devices at the moment are limited in precision, more so that accuracy expected from some programming or computing environments or from these numerical methods are or can be machine dependent. In fact, a part of the finding is that round-off propagation effects beyond a certain controllable order induces overwhelmingly delayed or even a severely retarded convergence speed which manifest glaringly as poor accuracy of these interval iteration methods in the computation of the zeros of a polynomial simultaneously. However, in this present consideration and even in the presence of overwhelming influence of round-offs, we give conditions under which convergence is still possible and derive the error/round-off relations along with the order/$R$-order of convergence of these methods with the results extended to similar interval iteration methods for computing the zeros of a polynomial simultaneously, especially to Bell’s interval methods for refinement of zeros that form a cluster. Our findings are instructive and quite revealing and supported by evidence from numerical experiments. The analysis is preferred in circular interval arithmetic.     

On the scaled newton method for the symmetric eigenvalue problem

For solving symmetric eigenvalue problems the scaled Newton method is proposed. The new algorithm is equivalent to the Rayleigh quotient iteration and its rate of convergence is cubic. Numerical experiments indicate that the scaled Newton method is very competitive with the projected Newton method, and produces, in the main, insignificantly smaller residua than the Rayleigh quotient iteration.     

Very fast and exact accumulation of products

The IFIP Working Group on Numerical Software and other scientists repeatedly requested that a future arithmetic standard should consider and specify an exact dot product (EDP) [The IFIP WG—IEEE 754R letter, dated September 4 (2007), The IFIP WG—IEEE P1788 letter, dated September 9 (2009)]. On 18 November 2009 the IEEE standards committee P1788 on interval arithmetic accepted a motion [Kulisch and Snyder (The exact dot product as basic tool for long interval arithmetic, passed on Nov 18, 2009 as official IEEE P1788 document)] for including the EDP into a future interval arithmetic standard. Actually the simplest and fastest way for computing a dot product is to compute it exactly. By pipelining, it can be computed in the time the processor needs to read the data, i.e., it comes with utmost speed. A hardware implementation of the EDP exceeds any approximate computation of the dot product in software by several orders of magnitude. By a sample illustration the paper informally specifies the implementation of the EDP on computers. While [Kulisch and Snyder (The exact dot product as basic tool for long interval arithmetic, passed on Nov 18, 2009 as official IEEE P1788 document)] defines what has to be provided, how to embed the EDP into the new standard IEEE 754, [IEEE Floating-Point Arithmetic Standard 754 (2008)] and how exceptions like NaN are to be dealt with, this article illustrates how the EDP can be implemented on computers. There is indeed no simpler way of accumulating a dot product. Any method that just computes an approximation also has to consider the relative values of the summands. This results in a more complicated method. The hardware needed for the EDP is comparable to that for a fast multiplier by an adder tree, accepted years ago and now standard technology in every modern processor. The EDP brings the same speedup for accumulations at comparable costs. In Numerical Analysis the dot product is ubiquitous. It is not merely a fundamental operation in all vector and matrix spaces. It is the EDP which makes residual correction effective. This has a direct and positive influence on all iterative solvers of systems of equations. The EDP is essential for fast long real and long interval arithmetic, as well as for assessing and managing uncertainty in computing. By operator overloading variable precision interval arithmetic is very easy to use. With it the result of every arithmetic expression can be guaranteed to a number of correct digits.     

Gaussian Laws for the Main Parameters of the Euclid Algorithms

We provide sharp estimates for the probabilistic behaviour of the main parameters of the Euclid Algorithms, both on polynomials and on integer numbers. We study in particular the distribution of the bit-complexity which involves two main parameters: digit-costs and length of remainders. We first show here that an asymptotic Gaussian law holds for the length of remainders at a fraction of the execution, which exhibits a deep regularity phenomenon. Then, we study in each framework—polynomials (P) and integer numbers (I)—two gcd algorithms, the standard one (S) which only computes the gcd, and the extended one (E) which also computes the Bezout pair, and is widely used for computing modular inverses. The extended algorithm is more regular than the standard one, and this explains that our results are more precise for the Extended algorithm: we exhibit an asymptotic Gaussian law for the bit-complexity of the extended algorithm, in both cases (P) and (I). We also prove that an asymptotic Gaussian law for the bit-complexity of the standard gcd in case (P), but we do not succeed obtaining a similar result in case (I). The integer study is more involved than the polynomial study, as it is usually the case. In the polynomial case, we deal with the central tools of the distributional analysis of algorithms, namely bivariate generating functions. In the integer case, we are led to dynamical methods, which heavily use the dynamical system underlying the number Euclidean algorithm, and its transfer operator. Baladi and Vallée (J. Number Theory 110(2):331–386, 2005) have recently designed a general framework for “distributional dynamical analysis”, where they have exhibited asymptotic Gaussian laws for a large family of parameters. However, this family does not contain neither the bit-complexity cost nor the size of remainders, and we have to extend their methods for obtaining our results. Even if these dynamical methods are not necessary in case (P), we explain how the polynomial dynamical system can be also used for proving our results. This provides a common framework for both analyses, which well explains the similarities and the differences between the two cases (P) and (I), for the algorithms themselves, and also for their analysis. An extended abstract of this paper can be found in Lhote and Vallée (Proceedings of LATIN’06, Lecture Notes in Computer Science, vol. 3887, pp. 689–702, 2006).     

Symbolic Preconditioning with Taylor Models: Some Examples

Deterministic global optimization with interval analysis involves using interval enclosures for ranges of the constraints, objective, and gradient to reject infeasible regions, regions without global optima, and regions without critical points; using interval Newton methods to converge on optimum-containing regions and to verify global optima.There are certain problems for which interval dependency leads to overestimation in the enclosures of the individual components, causing the optimization search to become prohibitively inefficient. As Hansen has observed earlier, in other problems, there is no overestimation in the individual components, but overestimation is introduced in the preconditioning in the interval Newton method.We examine these issues for a particular nonlinear systems problem that, to date, has defied numerical solution. To reduce overestimation, we use Taylor models. The Taylor models sometimes reduce individual overestimation but, consistent with Hansen's observations, especially reduce the overestimation due to preconditioning. From numerical experiments, we conclude that, in certain instances, Taylor models can greatly reduce both the number of subregions necessary to complete an exhaustive search and the total computational effort.     

Damping margins of interval polynomials

The zero locations of interval polynomials are examined. In particular, it is shown that a family of interval polynomials will have zeros only in the left sector if the real and imaginary parts of four specially constructed complex polynomials have an interlacing real zero property. This is significant for the analysis of uncertain systems, as the computation cost associated with checking the zero locations of interval polynomials will be greatly reduced. The results presented can be readily extended to more general stability regions where the real and imaginary parts of the polar plot are polynomial functions     

Verified High-Order Inversion of Functional Depedencies and Interval Newton Methods

A new method for computing verified enclosures of the inverses of given functions over large domains is presented. The approach is based on Taylor Model methods, and the sharpness of the enclosures scales with a high order of the domain. These methods have applications in the solution of implicit equations and the Taylor Model based integration of Differential Algebraic Equations (DAE) as well as other tasks where obtaining verified high-order models of inverse functions is required. The accuracy of Taylor model methods has been shown to scale with the (n + 1)-st order of the underlying domain, and as a consequence, they are particularly well suited to model functions over relatively large domains. Moreover, since Taylor models can control the cancellation and dependency problems (see Makino, K. and Berz, M.: Efficient Control of the Dependency Problem Based on Taylor Model Methods, Reliable Computing 5(1) (1999)) that often affect regular interval techniques, the new method can successfully deal with complicated multidimensional problems. As an application of these new methods, a high-order extension of the standard Interval Newton method that converges approximately with the (n + 1)-st order of the underlying domain is developed. Several examples showing various aspects of the practical behavior of the methods are given. This revised version was published online in August 2006 with corrections to the Cover Date.