TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Sun, 29 Jan 2023 15:41:38 GMT2023-01-29T15:41:38Z503661VSDP: Verified SemiDefinite Programming : user's guide ; beta version 0.1 for MATLAB 7.0http://hdl.handle.net/11420/8825Title: VSDP: Verified SemiDefinite Programming : user's guide ; beta version 0.1 for MATLAB 7.0
Authors: Jansson, Christian
Abstract: VSDP is a MATLAB software package for rigorously solving semidefinite programming problems. It expresses these problems in a notation closely related to the form given in textbooks and scientific papers. Functions for computing verified forward error bounds of the true optimal value and verified certificates of feasibility and infeasibility are provided. All rounding errors due to floating point arithmetic are taken into account. Computational results are given, including results for the SDPLIB benchmark problems. This package supports interval input data and sparse format.
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/11420/88252006-01-01T00:00:00ZVerified 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:00ZNear optimal subdivision algorithms for real root isolationhttp://hdl.handle.net/11420/7829Title: Near optimal subdivision algorithms for real root isolation
Authors: Sharma, Vikram; Batra, Prashant
Abstract: Isolating real roots of a square-free polynomial in a given interval is a fundamental problem. Subdivision based algorithms are a standard approach to solve this problem. E.g., Sturm's method, or various algorithms based on the Descartes's rule of signs. For isolating all the real roots of a degree n polynomial with root separation σ, the subdivision tree size of most of these algorithms is bounded by O(log 1/σ) (assume σ < 1). Recently Sagraloff (2012) and Sagraloff-Mehlhorn (2013) have developed algorithms that combine subdivision with Newton iteration to reduce the size of the subdivision tree to O(n(log(n log 1/σ))). Their algorithms and analysis crucially depend on the terminating predicates. We describe a subroutine that improves the running time of any subdivision algorithm for real root isolation. The subdivision tree size of our algorithm using predicates based on the Descartes's rule of signs is bounded by O(n log n). Our analysis differs in two key aspects from earlier approaches. First, we use the general technique of continuous amortization from Burr-Krahmer-Yap (2009), and hence the analysis extends to other predicates; and second, we use the geometry of clusters of roots instead of root bounds.
Wed, 24 Jun 2015 00:00:00 GMThttp://hdl.handle.net/11420/78292015-06-24T00: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:00ZSome applications of complex analysis to questions of stability and stabilizabilityhttp://hdl.handle.net/11420/8863Title: Some applications of complex analysis to questions of stability and stabilizability
Authors: Batra, Prashant
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/11420/88632006-01-01T00:00:00ZOn Goldberg's constant A2http://hdl.handle.net/11420/8654Title: On Goldberg's constant A2
Authors: Batra, Prashant
Mon, 01 Jan 2007 00:00:00 GMThttp://hdl.handle.net/11420/86542007-01-01T00:00:00ZGuaranteed accuracy for conic programming problems in vector latticeshttp://hdl.handle.net/11420/8652Title: Guaranteed accuracy for conic programming problems in vector lattices
Authors: Jansson, Christian
Abstract: This paper presents rigorous forward error bounds for linear conic optimization problems. The error bounds are formulated in a quite general framework; the underlying vector spaces are not required to be finite-dimensional, and the convex cones defining the partial ordering are not required to be polyhedral. In the case of linear programming, second order cone programming, and semidefinite programming specialized formulas are deduced yielding guaranteed accuracy. All computed bounds are completely rigorous because all rounding errors due to floating point arithmetic are taken into account. Numerical results, applications and software for linear and semidefinite programming problems are described.
Mon, 30 Jul 2007 00:00:00 GMThttp://hdl.handle.net/11420/86522007-07-30T00: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:00ZEntwurf und Implementierung einer gesicherten nachrichtenbasierten Kommunikation für verteilte Anwendungenhttp://hdl.handle.net/11420/8865Title: Entwurf und Implementierung einer gesicherten nachrichtenbasierten Kommunikation für verteilte Anwendungen
Authors: Rasenack, Robert; Teufel, Thomas
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/11420/88652006-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:00ZVerified solutions of two-point boundary value problems for nonlinear oscillatorshttp://hdl.handle.net/11420/7920Title: Verified solutions of two-point boundary value problems for nonlinear oscillators
Authors: Bünger, Florian
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11420/79202011-01-01T00:00:00ZAn IEEE 754-2008 decimal parallel and pipelined FPGA floating-point multiplierhttp://hdl.handle.net/11420/8531Title: An IEEE 754-2008 decimal parallel and pipelined FPGA floating-point multiplier
Authors: Baesler, Malte; Voigt, Sven-Ole; Teufel, Thomas
Abstract: Decimal floating point operations are important for applications that cannot tolerate errors from conversions between binary and decimal formats, for instance, scientific, commercial, and financial applications. In this paper we present an IEEE 754-2008 compliant parallel decimal floating-point multiplier designed to exploit the features of Virtex-5 FPGAs. It is an extension to a previously published decimal fixed-point multiplier. The decimal floating-point multiplier implements early estimation of the shift-left amount and efficient decimal rounding. Additionally, it provides all required rounding modes, exception handling, overflow, and gradual underflow. Several pipeline stages can be added to increase throughput. Furthermore, different modifications are analyzed including shifting by means of hard-wired multipliers and delayed carry propagation adders.
Wed, 01 Dec 2010 00:00:00 GMThttp://hdl.handle.net/11420/85312010-12-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:00ZA radix-10 digit recurrence division unit with a constant digit selection functionhttp://hdl.handle.net/11420/8530Title: A radix-10 digit recurrence division unit with a constant digit selection function
Authors: Baesler, Malte; Voigt, Sven-Ole; Teufel, Thomas
Abstract: Decimal floating point operations are important for applications that cannot tolerate errors from conversions between binary and decimal formats, for instance, scientific, commercial, and financial applications. In this work we present a radix-10 digit recurrence division algorithm that decomposes the quotient digits into three parts and requires only the computation of five and two times the divisor. Moreover, the divisor's multiples are selected without multiplexers and the digit selection functions are independent of the divisor's value and do not require a lookup table. The algorithm has been synthesized and verified on a Xilinx Virtex-5 FPGA and implementation results are given.
Mon, 29 Nov 2010 00:00:00 GMThttp://hdl.handle.net/11420/85302010-11-29T00: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:00ZGlobally convergent, iterative path-following for algebraic equationshttp://hdl.handle.net/11420/8532Title: Globally convergent, iterative path-following for algebraic equations
Authors: Batra, Prashant
Abstract: Homotopy methods are of great importance for the solution of systems of equations. It is a major problemto ensure well-defined iterations along the homotopy path. Many investigations have considered the complexityof path-following methods depending on the unknown distance of some given path to the variety of ill-posed problems. It is shown here that there exists a construction method for safe paths for a single algebraic equation. A safepath may be effectively determined with bounded effort. Special perturbation estimates for the zeros together withconvergence conditions for Newton's method in simultaneous mode allow our method to proceed on the safe path. This yields the first globally convergent, never-failing, uniformly iterative path-following algorithm. The maximumnumber of homotopy steps in our algorithm reaches a theoretical bound forecast by Shub and Smale i. e., the numberof steps is at most quadratic in the condition number. A constructive proof of the fundamental theorem of algebrameeting demands by Gauß, Kronecker and Weierstraß is a consequence of our algorithm.
Wed, 01 Dec 2010 00:00:00 GMThttp://hdl.handle.net/11420/85322010-12-01T00: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:00ZDynamically reconfigurable dataflow architecture for high-performance digital signal processing on multi-FPGA platformshttp://hdl.handle.net/11420/8656Title: Dynamically reconfigurable dataflow architecture for high-performance digital signal processing on multi-FPGA platforms
Authors: Voigt, Sven-Ole; Teufel, Thomas
Abstract: In this paper we present an FPGA-based dataflow architecture that both efficiently computes parallel algorithms using dedicated FPGA resources and scales well to multi-FPGA chip designs while the overall communication bandwidth increases. The basic idea is based on reconfiguration. In contrast to the concept of partially reconfiguring FPGAs, our approach is to connect computational units via a dynamically variable topology. The latter consists of dedicated switches which are individually controlled by simple shift registers. Hence, the computational result is a function of the currently configured interconnection pattern that can be updated within one single clock cycle. The scalability of this architecture is shown on a high-performance parallel FFT.
Mon, 12 Nov 2007 00:00:00 GMThttp://hdl.handle.net/11420/86562007-11-12T00: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:00ZSemidefinite relaxation approaches for the quadratic assignment problemhttp://hdl.handle.net/11420/1307Title: Semidefinite relaxation approaches for the quadratic assignment problem
Authors: Lange, Marko
Abstract: Diese Doktorarbeit behandelt bekannte und neue Relaxationstechniken für das quadratische Zuordnungsproblem, eines der schwierigsten zu lösenden NP-schweren Probleme der Kombinatorik. Der Schwerpunkt der Arbeit liegt auf neuen Ansätzen zur Approximation durch Semidefinite Optimierungsprobleme.; This thesis deals with known and new relaxation techniques for the quadratic assignment problem; a fundamental combinatorial optimization problem which is often considered as one of the hardest of NP-hard problems. The focus of this thesis is on techniques for the construction of semidefinite programming relaxations.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/11420/13072016-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 upper bounds for real proportional stabilising controllershttp://hdl.handle.net/11420/8723Title: On upper bounds for real proportional stabilising controllers
Authors: Batra, Prashant
Wed, 01 Jan 2003 00:00:00 GMThttp://hdl.handle.net/11420/87232003-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:00ZOn necessary conditions for real robust Schur-stabilityhttp://hdl.handle.net/11420/8725Title: On necessary conditions for real robust Schur-stability
Authors: Batra, Prashant
Abstract: A coefficient diameter of real Schur-stable interval polynomials is bounded using meromorphic functions. The resulting bound is the best possible. A known bound for the ratio of the two leading coefficients is improved for large diameters.
Sat, 01 Feb 2003 00:00:00 GMThttp://hdl.handle.net/11420/87252003-02-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:00ZAccelerating interval matrix multiplication by mixed precision arithmetichttp://hdl.handle.net/11420/7823Title: Accelerating interval matrix multiplication by mixed precision arithmetic
Authors: Ozaki, Katsuhisa; Ogita, Takeshi; Bünger, Florian; Oishi, Shin’ichi
Abstract: This paper is concerned with real interval arithmetic. We focus on interval matrix multiplication. Well-known algorithms for this purpose require the evaluation of several point matrix products to compute one interval matrix product. In order to save computing time we propose a method that modifies such known algorithm by partially using low-precision floating-point arithmetic. The modified algorithms work without significant loss of tightness of the computed interval matrix product but are about 30% faster than their corresponding original versions. The negligible loss of accuracy is rigorously estimated.
Wed, 01 Jul 2015 00:00:00 GMThttp://hdl.handle.net/11420/78232015-07-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:00ZRigorose Fehlerschranken für das Elektronenstrukturproblemhttp://hdl.handle.net/11420/2546Title: Rigorose Fehlerschranken für das Elektronenstrukturproblem
Authors: Ohlhus, Kai Torben
Abstract: Die vorliegende Doktorarbeit behandelt die Berechnung rigoroser Fehlerschranken für konische Optimierungsprobleme, einer Spezialform der konvexen Optimierung. Der Anwendungsschwerpunkt ist die Berechnung der Elektronenstruktur, insbesondere deren Grundzustandsenergie. Dies ist bis heute eine schwierig lösbare Problemstellung der Quantenchemie und kann als konisches Optimierungsproblem relaxiert werden. Es werden rigorose untere Fehlerschranken für das Elektronenstrukturproblem hergeleitet, welche alle Rundungsfehler miteinbeziehen und mit vernachlässigbarem Speicher- und Zeitaufwand für eine Vielzahl von Molekülen berechnet werden.; This thesis deals with the computation of rigorous error bounds for conic optimization problems, a special case of convex optimization. The focus of application is electronic structure calculation, especially the ground state energy. To this day it is a difficult problem of quantum chemistry, that can be relaxed to a conic optimization problem. Rigorous lower error bounds for the electronic structure problem are derived, that take all rounding errors into account and are computed for several molecules with negligible memory and time effort.
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11420/25462019-01-01T00:00:00ZQuantum information theory for engineers : free climbing through physics and probabilityhttp://hdl.handle.net/11420/2781Title: Quantum information theory for engineers : free climbing through physics and probability
Authors: Jansson, Christian
Abstract: Das Hauptziel dieser Ergänzungen zu meinem Buch ''Quantum Information Theory
for Engineers: An Interpretative Approach`` ist die Entwicklung einer Wahrscheinlichkeitstheorie, die sowohl auf klassische stochastische Experimente als auch auf quantenmechanische Probleme mit Interferenz anwendbar ist. Viele Paradoxien werden entmystifiziert. Die vierdimensionale Raumzeit wird durch die Trinität Zukunft, Gegenwart und Vergangenheit ersetzt. Dies führt zu einer Unterscheidung zwischen Ereignissen, Möglichkeiten und internen Möglichkeiten, sowie zu einer Zusammenführung der Dirac-Feynman Regeln mit der klassischen Wahrscheinlichkeitstheorie. Wir diskutieren Polarisations- und Spalt-Experimente, Quantenelektrodynamik, das Messproblem und Hardy's Paradoxon, ein Experiment das nach der klassischen Logik widersprüchlich ist, obwohl es durchgeführt wurde.; The aim of this supplement to my lecture notes ''Quantum Information Theory
for Engineers: An Interpretative Approach`` is to develop a probabilistic framework
that can be applied to classical stochastic problems as well as to quantum mechanical problems with interference phenomena. In particular, many paradoxes in quantum theory are demystified.
Our approach replaces spacetime by a trinity of time, namely future, present,
and past leading to a distinction between outcomes, possibilities, and internal possibilities. Our approach unifies the Dirac-Feynman rules with classical probability theory.
We discuss polarization and slit experiments, the measurement problem, quantum electrodynamics, and Hardy's paradox, a spectacular experimental setup where simple logical arguments about its physical constraints lead to a surprising contradiction.
Thu, 13 Jun 2019 00:00:00 GMThttp://hdl.handle.net/11420/27812019-06-13T00: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:00ZRigorous error bounds for the optimal value in semidefinite programminghttp://hdl.handle.net/11420/8659Title: Rigorous error bounds for the optimal value in semidefinite programming
Authors: Jansson, Christian; Chaykin, Denis; Keil, Christian
Abstract: A wide variety of problems in global optimization, combinatorial optimization, as well as systems and control theory can be solved by using linear and semidefinite programming. Sometimes, due to the use of floating point arithmetic in combination with ill-conditioning and degeneracy, erroneous results may be produced. The purpose of this article is to show how rigorous error bounds for the optimal value can be computed by carefully postprocessing the output of a linear or semidefinite programming solver. It turns out that in many cases the computational costs for postprocessing are small compared to the effort required by the solver. Numerical results are presented including problems from the SDPLIB and the NETLIB LP library; these libraries contain many ill-conditioned and real-life problems.
Sat, 01 Dec 2007 00:00:00 GMThttp://hdl.handle.net/11420/86592007-12-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:00ZOn verifed computation in combinatorial optimizationhttp://hdl.handle.net/11420/8665Title: On verifed computation in combinatorial optimization
Authors: Jansson, Christian
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/11420/86652005-01-01T00:00:00Z