TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Tue, 31 Jan 2023 09:37:22 GMT2023-01-31T09:37:22Z502071Verified bounds for the p-norm condition numberhttp://hdl.handle.net/11420/7659Title: Verified bounds for the p-norm condition number
Authors: Rump, Siegfried M.
Abstract: Methods to compute verified error bounds for the p-norm condition number of a matrix are discussed for p ∈ 1,2,∞ and the Frobenius norm. We consider the cases of a real or complex, point or interval input matrix. In the latter case the condition number of all matrices within the interval matrix are bounded. A special method for extremely illconditioned matrices is derived as well. Numerical results suggest that the quality of the bounds corresponds to the fact that the condition number of the condition number is the condition number.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/11420/76592014-01-01T00:00:00ZComputational error bounds for multiple or nearly multiple eigenvalueshttp://hdl.handle.net/11420/8828Title: Computational error bounds for multiple or nearly multiple eigenvalues
Authors: Rump, Siegfried M.
Abstract: In this paper bounds for clusters of eigenvalues of non-selfadjoint matrices are investigated. We describe a method for the computation of rigorous error bounds for multiple or nearly multiple eigenvalues, and for a basis of the corresponding invariant subspaces. The input matrix may be real or complex, dense or sparse. The method is based on a quadratically convergent Newton-like method; it includes the case of defective eigenvalues, uncertain input matrices and the generalized eigenvalue problem. Computational results show that verified bounds are still computed even if other eigenvalues or clusters are nearby the eigenvalues under consideration.
Thu, 15 Feb 2001 00:00:00 GMThttp://hdl.handle.net/11420/88282001-02-15T00:00:00ZImproved backward error bounds for LU and Cholesky factorizationshttp://hdl.handle.net/11420/7661Title: Improved backward error bounds for LU and Cholesky factorizations
Authors: Rump, Siegfried M.; Jeannerod, Claude Pierre
Abstract: Assuming standard floating-point arithmetic (in base β, precision p) and barring underflow and overflow, classical rounding error analysis of the LU or Cholesky factorization of an n×n matrix A provides backward error bounds of the form |ΔA| < γn|L̂||Û| or |ΔA| < γn+1|R̂T||R̂|. Here, L̂, Û, and R̂ denote the computed factors, and γn is the usual fraction nu/(1-nu) = nu+O(u2) with u the unit roundoff. Similarly, when solving an n×n triangular system Tx = b by substitution, the computed solution x̂ satisfies (T + ΔT)x̂ = b with |ΔT| < γn|T|. All these error bounds contain quadratic terms in u and limit n to satisfy either nu < 1 or (n + 1)u < 1. We show in this paper that the constants γn and γn+1 can be replaced by nu and (n + 1)u, respectively, and that the restrictions on n can be removed. To get these new bounds the main ingredient is a general framework for bounding expressions of the form |ρ - s|, where s is the exact sum of a floating-point number and n-1 real numbers and where ρ is a real number approximating the computed sum ŝ. By instantiating this framework with suitable values of ρ, we obtain improved versions of the well-known Lemma 8.4 from [N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, Philadelphia, 2002] (used for analyzing triangular system solving and LU factorization) and of its Cholesky variant. All our results hold for rounding to nearest with any tie-breaking strategy and whatever the order of summation.
Tue, 27 May 2014 00:00:00 GMThttp://hdl.handle.net/11420/76612014-05-27T00:00:00ZOn P-matriceshttp://hdl.handle.net/11420/8726Title: On P-matrices
Authors: Rump, Siegfried M.
Abstract: We present some necessary and sufficient conditions for a real matrix to be a P-matrix. They are based on the sign-real spectral radius and regularity of a certain interval matrix. We show that no minor can be left out when checking for P-property. Furthermore, a not necessarily exponential method for checking the P-property is given.
Thu, 10 Jan 2002 00:00:00 GMThttp://hdl.handle.net/11420/87262002-01-10T00:00:00ZVerified inclusion of a basis of the null spacehttp://hdl.handle.net/11420/7807Title: Verified inclusion of a basis of the null space
Authors: Kobayashi, R; Lange, Marko; Minamihata, Atsushi; Rump, Siegfried M.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/78072020-01-01T00:00:00ZComputing predecessor and successor in rounding to nearesthttp://hdl.handle.net/11420/8628Title: Computing predecessor and successor in rounding to nearest
Authors: Rump, Siegfried M.; Zimmermann, Paul; Boldo, Sylvie; Melquiond, Guillaume
Abstract: We give simple and efficient methods to compute and/or estimate the predecessor and successor of a floating-point number using only floating-point operations in rounding to nearest. This may be used to simulate interval operations, in which case the quality in terms of the diameter of the result is significantly improved compared to existing approaches.
Tue, 24 Feb 2009 00:00:00 GMThttp://hdl.handle.net/11420/86282009-02-24T00:00:00ZInterval arithmetic with fixed rounding modehttp://hdl.handle.net/11420/4394Title: Interval arithmetic with fixed rounding mode
Authors: Rump, Siegfried M.; Ogita, Takeshi; Morikura, Yusuke; Oishi, Shin’ichi
Abstract: We discuss several methods to simulate interval arithmetic operations using floating-point operations with fixed rounding mode. In particular we present formulas using only rounding to nearest and using only chop rounding (towards zero). The latter was the default and only rounding on GPU (Graphics Processing Unit) and cell processors, which in turn are very fast and therefore attractive in scientific computations.
Fri, 01 Jul 2016 00:00:00 GMThttp://hdl.handle.net/11420/43942016-07-01T00:00:00ZVerified computation of a disc containing exactly k roots of a univariate nonlinear functionhttp://hdl.handle.net/11420/8627Title: Verified computation of a disc containing exactly k roots of a univariate nonlinear function
Authors: Rump, Siegfried M.; Oishi, Shin’ichi
Fri, 01 Jan 2010 00:00:00 GMThttp://hdl.handle.net/11420/86272010-01-01T00:00:00ZAddendum to "on recurrences converging to the wrong limit in finite precision and some new examples"http://hdl.handle.net/11420/8157Title: Addendum to "on recurrences converging to the wrong limit in finite precision and some new examples"
Authors: Rump, Siegfried M.
Abstract: In a recent paper [Electron. Trans. Numer. Anal, 52 (2020), pp. 358-369], we analyzed Muller's famous recurrence, where, for particular initial values, the iteration over real numbers converges to a repellent fixed point, whereas finite precision arithmetic produces a different result, the attracting fixed point. We gave necessary and sufficient conditions for such recurrences to produce only nonzero iterates. In the above-mentioned paper, an example was given where only finitely many terms of the recurrence over R are well defined, but floating-point evaluation indicates convergence to the attracting fixed point. The input data of that example, however, are not representable in binary floating-point, and the question was posed whether such examples exist with binary representable data. This note answers that question in the affirmative.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/81572020-01-01T00:00:00ZAddendum to “Estimates of the determinant of a perturbed identity matrix” [Linear Algebra Appl. 558 (2018) 101–107]http://hdl.handle.net/11420/5276Title: Addendum to “Estimates of the determinant of a perturbed identity matrix” [Linear Algebra Appl. 558 (2018) 101–107]
Authors: Rump, Siegfried M.; Batra, Prashant
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11420/52762019-01-01T00:00:00ZFaithfully Rounded Floating-point Computationshttp://hdl.handle.net/11420/7628Title: Faithfully Rounded Floating-point Computations
Authors: Lange, Marko; Rump, Siegfried M.
Abstract: We present a pair arithmetic for the four basic operations and square root. It can be regarded as a simplified, more-efficient double-double arithmetic. The central assumption on the underlying arithmetic is the first standard model for error analysis for operations on a discrete set of real numbers. Neither do we require a floating-point grid nor a rounding to nearest property. Based on that, we define a relative rounding error unit u and prove rigorous error bounds for the computed result of an arbitrary arithmetic expression depending on u, the size of the expression, and possibly a condition measure. In the second part of this note, we extend the error analysis by examining requirements to ensure faithfully rounded outputs and apply our results to IEEE 754 standard conform floating-point systems. For a class of mathematical expressions, using an IEEE 754 standard conform arithmetic with base β, the result is proved to be faithfully rounded for up to 1 / √βu-2 operations. Our findings cover a number of previously published algorithms to compute faithfully rounded results, among them Horner's scheme, products, sums, dot products, or Euclidean norm. Beyond that, several other problems can be analyzed, such as polynomial interpolation, orientation problems, Householder transformations, or the smallest singular value of Hilbert matrices of large size.
Tue, 01 Sep 2020 00:00:00 GMThttp://hdl.handle.net/11420/76282020-09-01T00:00:00ZConservatism of the circle criterion-solution of a problem posed by A. Megretskihttp://hdl.handle.net/11420/8839Title: Conservatism of the circle criterion-solution of a problem posed by A. Megretski
Authors: Rump, Siegfried M.
Abstract: In the collection of open problems in mathematical systems and control theory [1], Megretski poses a problem related to the degree of conservativism of the well-known circle criterion follows. We solve this problem.
Mon, 01 Oct 2001 00:00:00 GMThttp://hdl.handle.net/11420/88392001-10-01T00:00:00ZError-free transformations and ill-conditioned problemshttp://hdl.handle.net/11420/8629Title: Error-free transformations and ill-conditioned problems
Authors: Rump, Siegfried M.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/11420/86292009-01-01T00:00:00ZRigorous results in electronic structure calculationshttp://hdl.handle.net/11420/7814Title: Rigorous results in electronic structure calculations
Authors: Chaykin, Denis; Jansson, Christian; Keil, Frerich; Lange, Marko; Ohlhus, Kai Torben; Rump, Siegfried M.
Abstract: Electronic structure calculations, in particular the computation of the ground state energy, lead to challenging problems in optimization. These problems are of enormous importance in quantum chemistry for calculations of properties of solids and molecules. Minimization methods for computing the ground state energy can be developed by employing a variational approach, where the second-order reduced density matrix defines the variable. This concept leads to large-scale semidefinite programming problems that provide a lower bound for the ground state energy. Upper bounds of the ground state energy can be calculated for example with the Hartree-Fock method. However, Nakata, Nakatsuji, Ehara, Fukuda, Nakata, and Fujisawa observed, that due to numerical errors the semidefinite solver produced erroneous results with a lower bound significantly larger than the Hartree-Fock upper bound. Violations within one mhartree were observed. We present here a method for solving electronic structure problems where all numerical errors are taken into consideration. In particular this method provides rigorous error bounds without violations as mentioned above.
Tue, 01 Nov 2016 00:00:00 GMThttp://hdl.handle.net/11420/78142016-11-01T00:00:00ZOn recurrences converging to the wrong limit in finite precision and some new exampleshttp://hdl.handle.net/11420/7747Title: On recurrences converging to the wrong limit in finite precision and some new examples
Authors: Rump, Siegfried M.
Abstract: In 1989, Jean-Michel Muller gave a famous example of a recurrence where, for particular initial values, the iteration over real numbers converges to a repellent fixed point, whereas finite precision arithmetic produces a different result, the attracting fixed point. We analyze recurrences in that spirit and remove a gap in previous arguments in the literature, that is, the recursion must be well defined. The latter is known as the Skolem problem. We identify initial values producing a limit equal to the repellent fixed point, show that in every ε-neighborhood of such initial values the recurrence is not well defined, and characterize initial values for which the recurrence is well defined. We give some new examples in that spirit. For example, the correct real result, i.e., the repellent fixed point, may be correctly computed in bfloat, half, single, double, formerly extended precision (80 bit format), binary128 as well as many formats of much higher precision. Rounding errors may be beneficial by introducing some regularizing effect.
Fri, 10 Jul 2020 00:00:00 GMThttp://hdl.handle.net/11420/77472020-07-10T00:00:00ZUltimately fast accurate summationhttp://hdl.handle.net/11420/8631Title: Ultimately fast accurate summation
Authors: Rump, Siegfried M.
Abstract: We present two new algorithms FastAccSum and FastPrecSum, one to compute a faithful rounding of the sum of floating-point numbers and the other for a result "as if" computed in K-fold precision. Faithful rounding means the computed result either is one of the immediate floating-point neighbors of the exact result or is equal to the exact sum if this is a floating-point number. The algorithms are based on our previous algorithms AccSum and PrecSum and improve them by up to 25%. The first algorithm adapts to the condition number of the sum; i.e., the computing time is proportional to the difficulty of the problem. The second algorithm does not need extra memory, and the computing time depends only on the number of summands and K. Both algorithms are the fastest known in terms of flops. They allow good instruction-level parallelism so that they are also fast in terms of measured computing time. The algorithms require only standard floating-point addition, subtraction, and multiplication in one working precision, for example, double precision.
Fri, 04 Sep 2009 00:00:00 GMThttp://hdl.handle.net/11420/86312009-09-04T00:00:00ZConvergence of Rump's method for inverting arbitrarily ill-conditioned matriceshttp://hdl.handle.net/11420/8655Title: Convergence of Rump's method for inverting arbitrarily ill-conditioned matrices
Authors: Oishi, Shin’ichi; Tanabe, Kunio; Ogita, Takeshi; Rump, Siegfried M.
Abstract: In this paper, the problem of inverting regular matrices with arbitrarily large condition number is treated in double precision defined by IEEE 754 floating point standard. In about 1984, Rump derived a method for inverting arbitrarily ill-conditioned matrices. The method requires the possibility to calculate a dot product in higher precision. Rump's method is of theoretical interest. Rump made it clear that inverting an arbitrarily ill-conditioned matrix in single or double precision does not produce meaningless numbers, but contains a lot of information in it. Rump's method uses such inverses as preconditioners. Numerical experiments exhibit that Rump's method converges rapidly for various matrices with large condition numbers. Why Rump's method is so efficient for inverting arbitrarily ill-conditioned matrices is a little mysterious. Thus, to prove its convergence is an interesting problem in numerical error analysis. In this article, a convergence theorem is presented for a variant of Rump's method.
Sun, 11 Jun 2006 00:00:00 GMThttp://hdl.handle.net/11420/86552006-06-11T00:00:00ZStructured perturbations part I: normwise distanceshttp://hdl.handle.net/11420/8729Title: Structured perturbations part I: normwise distances
Authors: Rump, Siegfried M.
Abstract: In this paper we study the condition number of linear systems, the condition number of matrix inversion, and the distance to the nearest singular matrix, all problems with respect to normwise structured perturbations. The structures under investigation are symmetric, persymmetric, skewsymmetric, symmetric Toeplitz, general Toeplitz, circulant, Hankel, and persymmetric Hankel matrices (some results on other structures such as tridiagonal and tridiagonal Toeplitz matrices, both symmetric and general, are presented as well). We show that for a given matrix the worst case structured condition number for all right-hand sides is equal to the unstructured condition number. For a specific right-hand side we give various explicit formulas and estimations for the condition numbers for linear systems, especially for the ratio of the condition numbers with respect to structured and unstructured perturbations. Moreover, the condition number of matrix inversion is shown to be the same for structured and unstructured perturbations, and the same is proved for the distance to the nearest singular matrix. It follows a generalization of the classical Eckart-Young theorem, namely, that the reciprocal of the condition number is equal to the distance to the nearest singular matrix for all structured perturbations mentioned above.
Tue, 09 Mar 2004 00:00:00 GMThttp://hdl.handle.net/11420/87292004-03-09T00:00:00ZAccurate matrix multiplication with multiple floating-point numbershttp://hdl.handle.net/11420/8653Title: Accurate matrix multiplication with multiple floating-point numbers
Authors: Ozaki, Katsuhisa; Ogita, Takeshi; Rump, Siegfried M.; Oishi, Shin’ichi
Mon, 01 Jan 2007 00:00:00 GMThttp://hdl.handle.net/11420/86532007-01-01T00:00:00ZFast verification algorithms in Matlabhttp://hdl.handle.net/11420/8844Title: Fast verification algorithms in Matlab
Authors: Rump, Siegfried M.
Mon, 01 Jan 2001 00:00:00 GMThttp://hdl.handle.net/11420/88442001-01-01T00:00:00ZKleine Fehlerschranken bei Matrixproblemenhttp://hdl.handle.net/11420/323Title: Kleine Fehlerschranken bei Matrixproblemen
Authors: Rump, Siegfried M.
Abstract: Kleine Fehlerschranken bei Matrixproblemen
Tue, 01 Jan 1980 00:00:00 GMThttp://hdl.handle.net/11420/3231980-01-01T00:00:00ZVerified sharp bounds for the real gamma function over the entire floating-point rangehttp://hdl.handle.net/11420/7878Title: Verified sharp bounds for the real gamma function over the entire floating-point range
Authors: Rump, Siegfried M.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/11420/78782014-01-01T00:00:00ZGeneralization of error-free transformation for matrix multiplication and its applicationhttp://hdl.handle.net/11420/7883Title: Generalization of error-free transformation for matrix multiplication and its application
Authors: Ozaki, Katsuhisa; Ogita, Takeshi; Oishi, Shin’ichi; Rump, Siegfried M.
Tue, 01 Jan 2013 00:00:00 GMThttp://hdl.handle.net/11420/78832013-01-01T00:00:00ZOn the generation of very ill-conditioned integer matriceshttp://hdl.handle.net/11420/7927Title: On the generation of very ill-conditioned integer matrices
Authors: Nishi, Tetsuo; Rump, Siegfried M.; Oishi, Shin’ichi
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11420/79272011-01-01T00:00:00ZInversion of extremely ill-conditioned matrices in floating-pointhttp://hdl.handle.net/11420/8630Title: Inversion of extremely ill-conditioned matrices in floating-point
Authors: Rump, Siegfried M.
Abstract: Let an n × n matrix A of floating-point numbers in some format be given. Denote the relative rounding error unit of the given format by eps. Assume A to be extremely ill-conditioned, that is cond(A) > eps-1. In about 1984 I developed an algorithm to calculate an approximate inverse of A solely using the given floating-point format. The key is a multiplicative correction rather than a Newton-type additive correction. I did not publish it because of lack of analysis. Recently, in [9] a modification of the algorithm was analyzed. The present paper has two purposes. The first is to present reasoning how and why the original algorithm works. The second is to discuss a quite unexpected feature of floating-point computations, namely, that an approximate inverse of an extraordinary ill-conditioned matrix still contains a lot of useful information. We will demonstrate this by inverting a matrix with condition number beyond 10300 solely using double precision. This is a workout of the invited talk at the SCAN meeting 2006 in Duisburg.
Thu, 01 Oct 2009 00:00:00 GMThttp://hdl.handle.net/11420/86302009-10-01T00:00:00ZComputable backward error bounds for basic algorithms in linear algebrahttp://hdl.handle.net/11420/7826Title: Computable backward error bounds for basic algorithms in linear algebra
Authors: Rump, Siegfried M.
Abstract: Standard error estimates in numerical linear algebra are often of the form γk|R||S| where R,S are known matrices and γk:=ku/(1-u) with u denoting the relative rounding error unit. Recently we showed that for a number of standard problems γk can be replaced by ku for any order of computation and without restriction on the dimension. Such problems include LU- and Cholesky decomposition, triangular system solving by substitution, matrix multiplication and more. The theoretical bound implies a practically computable bound by estimating the error in the floating-point computation of ku|R||S|. Standard techniques, however, imply again a restriction on the dimension. In this note we derive simple computable bounds being valid without restriction on the dimension. As the bounds are mathematically rigorous, they may serve in computer assisted proofs.
Wed, 01 Jul 2015 00:00:00 GMThttp://hdl.handle.net/11420/78262015-07-01T00:00:00ZSign controlled solvers for the absolute value equation with an application to support vector machineshttp://hdl.handle.net/11420/7808Title: Sign controlled solvers for the absolute value equation with an application to support vector machines
Authors: Lehmann, Lutz; Radons, Manuel; Rump, Siegfried M.; Strohm, Christian
Abstract: Let A be a real n n matrix and z; b 2 Rn. The piecewise linear equation system z Ajzj = b is called an absolute value equation. It is equivalent to the general linear complementarity problem, and thus NP hard in general. Concerning the latter problem, three solvers are presented: One direct, one semi-iterative and one discrete variant of damped Newton. Their previously proved ranges of correctness and convergence, respectively, are extended. Their performance is compared on instances of the XOR separation problem for support vector machines which can be reformulated as an absolute value equation.
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/11420/78082017-01-01T00:00:00ZOptimal scaling for p-norms and componentwise distance to singularityhttp://hdl.handle.net/11420/8727Title: Optimal scaling for p-norms and componentwise distance to singularity
Authors: Rump, Siegfried M.
Abstract: We give lower and upper bounds for the optimal p-norm condition number achievable by two-sided diagonal scalings. There are no assumptions on the irreducibility of certain matrices. The bounds are shown to be optimal for the 2-norm. For the 1-norm and inf-norm the (known) exact value of the optimal condition number is confirmed. We give means how to calculate the minimizing diagonal matrices. Furthermore, a class of new lower bounds for the componentwise distance to the nearest singular matrix is given. They are shown to be superior to existing ones.
Wed, 01 Jan 2003 00:00:00 GMThttp://hdl.handle.net/11420/87272003-01-01T00:00:00ZComputer-assisted proofs and self-validating methodshttp://hdl.handle.net/11420/8668Title: Computer-assisted proofs and self-validating methods
Authors: Rump, Siegfried M.
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/11420/86682005-01-01T00:00:00ZNumerical verification method for arbitrarily Ill-conditioned linear systemshttp://hdl.handle.net/11420/8674Title: Numerical verification method for arbitrarily Ill-conditioned linear systems
Authors: Ohta, Takahisa; Ogita, Takeshi; Rump, Siegfried M.; Oishi, Shin’ichi
Sun, 25 Sep 2005 00:00:00 GMThttp://hdl.handle.net/11420/86742005-09-25T00:00:00ZEvaluierung von Hedge-Effektivitätstestshttp://hdl.handle.net/11420/8664Title: Evaluierung von Hedge-Effektivitätstests
Authors: Hailer, A. C.; Rump, Siegfried M.
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/11420/86642005-01-01T00:00:00ZPositive entries of stable matriceshttp://hdl.handle.net/11420/8667Title: Positive entries of stable matrices
Authors: Friedland, Shmuel; Hershkowitz, Daniel; Rump, Siegfried M.
Abstract: The question of how many elements of a real positive stable matrix must be positive is investigated. It is shown that any real stable matrix of order greater than 1 has at least two positive entries. Furthermore, for every stable spectrum of cardinality greater than 1 there exists a real matrix with that spectrum with exactly two positive elements, where all other elements of the matrix can be chosen to be negative.
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/11420/86672005-01-01T00:00:00ZFast verification for all eigenpairs in symmetric positive definite generalized eigenvalue problemshttp://hdl.handle.net/11420/8533Title: Fast verification for all eigenpairs in symmetric positive definite generalized eigenvalue problems
Authors: Miyajima, Shinya; Ogita, Takeshi; Rump, Siegfried M.; Oishi, Shin’ichi
Abstract: A fast method for enclosing all eigenpairs in symmetric positive definite generalized eigenvalue problems is proposed. Firstly theorems on verifying all eigenvalues are presented. Next a theorem on verifying all eigenvectors is presented. The proposed method is developed based on these theorems. Numerical results are presented showing the efficiency of the proposed method. As an application of the proposed method, an efficient method of enclosing all eigenpairs in the quadratic eigenvalue problem is also sketched.
Tue, 01 Jun 2010 00:00:00 GMThttp://hdl.handle.net/11420/85332010-06-01T00:00:00ZComputer-assisted proofs IIhttp://hdl.handle.net/11420/8943Title: Computer-assisted proofs II
Authors: Rump, Siegfried M.
Thu, 01 Jan 2004 00:00:00 GMThttp://hdl.handle.net/11420/89432004-01-01T00:00:00ZHigher order computer arithmetichttp://hdl.handle.net/11420/8671Title: Higher order computer arithmetic
Authors: Rump, Siegfried M.
Abstract: The floating-point arithmetic on computers is designed to approximate the corresponding operations over the real numbers as close as possible. In this paper it is shown by means of counterexamples that this need not to be true for existing machines. For achieving good numerical results a floating-point arithmetic approximating the real operations as close as possible is probably best. For achieving verifications on computers, at least a precisely defined computer arithmetic is indispensable. In this paper we first introduce the Kulisch/Miranker theory, which represents a sound basis for computer arithmetic. Each operation is precisely defined and, moreover, is of maximum accuracy. That means, the, computed result is the floating-point number of the working precision closest to the infinite precise result. The theory also covers directed roundings allowing computations with intervals. These properties hold true for the floating-point numbers of single and double precision as well as for the vectors, matrices and complex extensions over those. In the second part of the paper we demonstrate the theoretical basis for what we call "Higher Order Computer Arithmetic'. This is an inclusion theory allowing the development of algorithms to compute bounds for the solution of various problems in numerical analysis. These bounds are automatically verified to be correct and they are of high accuracy. Very often they are of maximum accuracy, that means the left and right bounds of all components of the solution are adjacent in the floating-point screen. Moreover existence and uniqueness of a solution within the computed bounds is automatically verified by the algorithm. If this verification is not possible, a respective message is given. We develop the theory and give algorithms for the solution of systems of linear and nonlinear equations. As demonstrated by examples even for extremely ill-conditioned problems existence and uniqueness of the solution is verified within bounds of least significant bit accuracy.
Tue, 01 Jan 1985 00:00:00 GMThttp://hdl.handle.net/11420/86711985-01-01T00:00:00ZAccurate sum and dot producthttp://hdl.handle.net/11420/8670Title: Accurate sum and dot product
Authors: Ogita, Takeshi; Rump, Siegfried M.; Oishi, Shin’ichi
Abstract: Algorithms for summation and dot product of floating-point numbers are presented which are fast in terms of measured computing time. We show that the computed results are as accurate as if computed in twice or AT-fold working precision, K ≥ 3. For twice the working precision our algorithms for summation and dot product are some 40% faster than the corresponding XBLAS routines while sharing similar error estimates. Our algorithms are widely applicable because they require only addition, subtraction, and multiplication of floating-point numbers in the same working precision as the given data. Higher precision is unnecessary, algorithms are straight loops without branch, and no access to mantissa or exponent is necessary.
Fri, 25 Nov 2005 00:00:00 GMThttp://hdl.handle.net/11420/86702005-11-25T00:00:00ZVerified error bounds for multiple roots of systems of nonlinear equationshttp://hdl.handle.net/11420/8535Title: Verified error bounds for multiple roots of systems of nonlinear equations
Authors: Rump, Siegfried M.; Graillat, Stef
Abstract: It is well known that it is an ill-posed problem to decide whether a function has a multiple root. Even for a univariate polynomial an arbitrary small perturbation of a polynomial coefficient may change the answer from yes to no. Let a system of nonlinear equations be given. In this paper we describe an algorithm for computing verified and narrow error bounds with the property that a slightly perturbed system is proved to have a double root within the computed bounds. For a univariate nonlinear function f we give a similar method also for a multiple root. A narrow error bound for the perturbation is computed as well. Computational results for systems with up to 1000 unknowns demonstrate the performance of the methods.
Fri, 16 Oct 2009 00:00:00 GMThttp://hdl.handle.net/11420/85352009-10-16T00:00:00ZVerified solution of linear systems without directed roundinghttp://hdl.handle.net/11420/8672Title: Verified solution of linear systems without directed rounding
Authors: Ogita, Takeshi; Rump, Siegfried M.; Oishi, Shin’ichi
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/11420/86722005-01-01T00:00:00ZComponentwise verified solutions of linear system suited for Javahttp://hdl.handle.net/11420/8666Title: Componentwise verified solutions of linear system suited for Java
Authors: Ozaki, Katsuhisa; Ogita, Takeshi; Miyajima, Shinya; Oishi, Shin’ichi; Rump, Siegfried M.
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/11420/86662005-01-01T00:00:00ZNumerical method for dense linear systems with arbitrariliy Ill-conditioned matriceshttp://hdl.handle.net/11420/8673Title: Numerical method for dense linear systems with arbitrariliy Ill-conditioned matrices
Authors: Ohta, Takahisa; Ogita, Takeshi; Rump, Siegfried M.; Oishi, Shin’ichi
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/11420/86732005-01-01T00:00:00ZInterval arithmeticshttp://hdl.handle.net/11420/7828Title: Interval arithmetics
Authors: Rump, Siegfried M.
Sat, 21 Nov 2015 00:00:00 GMThttp://hdl.handle.net/11420/78282015-11-21T00:00:00ZVerified solutions of extremely Ill-conditioned linear systemshttp://hdl.handle.net/11420/8686Title: Verified solutions of extremely Ill-conditioned linear systems
Authors: Ohta, Takahisa; Oishi, Shin’ichi; Ogita, Takeshi; Rump, Siegfried M.
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/11420/86862005-01-01T00:00:00ZPerron-Frobenius theory for complex matriceshttp://hdl.handle.net/11420/8728Title: Perron-Frobenius theory for complex matrices
Authors: Rump, Siegfried M.
Abstract: The purpose of this paper is to present a unified Perron-Frobenius Theory for nonnegative, for real not necessarily nonnegative and for general complex matrices. The sign-real spectral radius was introduced for general real matrices. This quantity was shown to share certain properties with the Perron root of nonnegative matrices. In this paper we introduce the sign-complex spectral radius. Again, this quantity extends many properties of the Perron root of nonnegative matrices to general complex matrices. Various characterizations will be given, and many open problems remain.
Wed, 04 Dec 2002 00:00:00 GMThttp://hdl.handle.net/11420/87282002-12-04T00:00:00ZA model problem for global optimizationhttp://hdl.handle.net/11420/8537Title: A model problem for global optimization
Authors: Rump, Siegfried M.
Fri, 01 Jan 2010 00:00:00 GMThttp://hdl.handle.net/11420/85372010-01-01T00:00:00ZStructured perturbations part II: componentwise distanceshttp://hdl.handle.net/11420/8730Title: Structured perturbations part II: componentwise distances
Authors: Rump, Siegfried M.
Abstract: In the second part of this paper we study condition numbers with respect to componentwise perturbations in the input data for linear systems and for matrix inversion, and the distance to the nearest singular matrix. The structures under investigation are linear structures, namely symmetric, persymmetric, skewsymmetric, symmetric Toeplitz, general Toeplitz, circulant, Hankel, and persymmetric Hankel structures. We give various formulas and estimations for the condition numbers. For all structures mentioned except circulant structures we give explicit examples of linear systems Aεx = b with parameterized matrix Aε such that the unstructured componentwise condition number is script O sigh(ε-1) and the structured componentwise condition number is script O sign(1). This is true for the important case of componentwise relative perturbations in the matrix and in the right-hand side. We also prove corresponding estimations for circulant structures. Moreover, bounds for the condition number of matrix inversion are given. Finally, we give for all structures mentioned above explicit examples of parameterized (structured) matrices Aε such that the (componentwise) condition number of matrix inversion is script O sign(ε-1), but the componentwise distance to the nearest singular matrix is script O sign(1). This is true for componentwise relative perturbations. It shows that, unlike the normwise case, there is no reciprocal proportionality between the componentwise condition number and the distance to the nearest singular matrix.
Tue, 09 Mar 2004 00:00:00 GMThttp://hdl.handle.net/11420/87302004-03-09T00:00:00ZError bounds for extremely ill-conditioned problemshttp://hdl.handle.net/11420/8890Title: Error bounds for extremely ill-conditioned problems
Authors: Rump, Siegfried M.
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/11420/88902006-01-01T00:00:00ZOn Nishi's conditions for Ω-propertyhttp://hdl.handle.net/11420/8702Title: On Nishi's conditions for Ω-property
Authors: Rump, Siegfried M.
Abstract: The concept of an Ω-matrix was introduced by Nishi in order to estimate the number of solutions of a resistive circuit containing active elements. He gave a finite characterization by means of four conditions which are all satisfied if and only if the matrix under investigation is an Ω-matrix. In this note we show that none of the four conditions can be omitted.
Wed, 01 Jan 2003 00:00:00 GMThttp://hdl.handle.net/11420/87022003-01-01T00:00:00ZIterative refinement for ill-conditioned linear equationshttp://hdl.handle.net/11420/8600Title: Iterative refinement for ill-conditioned linear equations
Authors: Oishi, Shin’ichi; Ogita, Takeshi; Rump, Siegfried M.
Tue, 01 Jan 2008 00:00:00 GMThttp://hdl.handle.net/11420/86002008-01-01T00:00:00ZShort biography of Shmuel Friedland for his special LAA volumehttp://hdl.handle.net/11420/7890Title: Short biography of Shmuel Friedland for his special LAA volume
Authors: Berman, Abraham; Krattenthaler, Christian; Rump, Siegfried M.; Spitkovsky, Ilya; Zhang, Fuzhen
Wed, 30 Sep 2009 00:00:00 GMThttp://hdl.handle.net/11420/78902009-09-30T00:00:00ZRigorous and portable standard functionshttp://hdl.handle.net/11420/8846Title: Rigorous and portable standard functions
Authors: Rump, Siegfried M.
Abstract: Today's floating point implementations of elementary transcendental functions are usually very accurate. However, with few exceptions, the actual accuracy is not known. In the present paper we describe a rigorous, accurate, fast and portable implementation of the elementary standard functions based on some existing approximate standard functions. The scheme is outlined for IEEE 754, but not difficult to adapt to other floating point formats. A Matlab implementation is available on the net. Accuracy of the proposed algorithms can be rigorously estimated. As an example we prove that the relative accuracy of the exponential function is better than 2.07 eps in a slightly reduced argument range (eps denoting the relative rounding error unit). Otherwise, extensive computational tests suggest for all elementary functions and all suitable arguments an accuracy better than about 3 eps.
Mon, 01 Jan 2001 00:00:00 GMThttp://hdl.handle.net/11420/88462001-01-01T00:00:00Z