377 results
Filters
Settings
Now showing1 - 10 of 377
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Verified error bounds for sparse systems part II: inertia-based bounds, least squares and nonlinear systemsVerification methods provide mathematically correct error bounds for the solution of a numerical problem. That includes the proof of solvability of the problem and often uniqueness of the solution within the computed bounds. There are many verification methods for standard problems in numerical analysis, including linear and nonlinear systems of equations, matrix decompositions, eigenproblems, local and global optimization, and ordinary and partial differential equations. Many of those verification methods are included in INTLAB, the MATLAB/Octave toolbox for reliable computing. Despite many efforts, the solution of general sparse linear systems was an open problem. In Part I of this note, we presented an algorithm computing verified bounds for the solution of general real or complex sparse linear systems with condition number up to the limit [Formula: see text] in double precision. That algorithm splits into three subalgorithms for symmetric positive definite, symmetric indefinite, and general input matrix [Formula: see text]. It is based on a mathematically correct lower bound on the smallest singular value [Formula: see text]. In this Part II, we use a method published by the author in 1995 based on the inertia of a symmetric matrix. A key point is, as in Part I, a factorization [Formula: see text] such that [Formula: see text] and [Formula: see text] have identical sets of singular values with the smallest one close to [Formula: see text]. Numerical evidence suggests that the method is often a little slower than that in Part I, however, more robust. That means, for some of the few cases where the method in Part I could not compute verified bounds successfully, the method in this Part II succeeded. Furthermore, we show how to compute inclusions with almost maximal accuracy for all entries, i.e., all bounds differ by few bits, that is, based on a fast method to compute accurate approximations and bounds for extremely ill-conditioned dot products using a very efficient MATLAB implementation. We show how to treat a system with nearly symmetric input matrix in the sense that [Formula: see text] is small compared to [Formula: see text]. That is useful if symmetry is lost due to rounding and may improve the performance significantly. We show that Algorithm “verifySparseNearSym1” in Part I of the note is correct for unsymmetric input matrix without change. Moreover, algorithms are given to compute verified error bounds for a least squares problem and an underdetermined system of linear equations with sparse input matrix. Furthermore, we show how to compute verified error bounds for the solution of a system of nonlinear equations with sparse Jacobian. In all cases, the algorithms for sparse square linear systems of Part I and this Part II can be used.Publicationtype: Journal Article3 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Verified error bounds for sparse systems part I: the splitting of a matrix into two factorsVerification methods provide mathematically correct error bounds for the solution of a numerical problem. That includes the proof of solvability of the problem and often uniqueness of the solution within the computed bounds. There are many verification methods for standard problems in numerical analysis, including linear and nonlinear systems of equations, matrix decompositions, eigenproblems, local and global optimization, and ordinary and partial differential equations. Many of those are included in INTLAB, the MATLAB/Octave toolbox for reliable computing. Despite several efforts, the verified solution of general sparse linear systems was an open problem. There are satisfactory algorithms for systems with symmetric positive definite input matrix. To that end error bounds for the solution of [Formula: see text] with general matrix [Formula: see text] could be computed using [Formula: see text], but that reduces the applicability in double precision to matrices with condition number up to [Formula: see text]. We give in this note an algorithm to compute entrywise error bounds for the solution of general real or complex sparse systems with condition number up to the limit [Formula: see text]. Our algorithm splits into three subalgorithms for symmetric positive definite, symmetric indefinite, and general input matrix [Formula: see text]. It is based on a mathematically correct lower bound on the smallest singular value [Formula: see text]. A key point is a factorization [Formula: see text] such that [Formula: see text] and [Formula: see text] have identical sets of singular values with the smallest one close to [Formula: see text]. A mathematically correct lower bound on [Formula: see text] is then computed using [Formula: see text]. Numerical evidence suggests that bounds for the solution of a linear system are computed for condition numbers up to [Formula: see text], and that often the bounds for all entries are close to maximally accurate, i.e., the bounds differ by few bits. We present a new a priori error bound based on Perron–Frobenius theory on the residual of a floating-point Cholesky decomposition which improves on existing ones by some two orders of magnitude. Our three subalgorithms benefit from this new bound. Based on the results in this Part I, an alternative approach will be presented in Part II of this note. Those methods are somewhat simpler, but often slower. However, they seem to be more robust, i.e., produce verified inclusions where the methods of Part I fail. Both approaches for square linear systems will be used in Part II of this note to compute verified error bounds for the solution of least squares problems and for underdetermined linear systems. Moreover, inclusions of the solution of general real or complex systems of nonlinear equations with sparse Jacobi matrix are computed by transforming the problem into a linear system with point matrix and interval right-hand side.Publicationtype: Journal Article19 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , INTLAB: the Matlab/Octave toolbox for reliable computingThe Matlab/Octave toolbox INTLAB offers many so-called verification algorithms the results of which are correct with mathematical certainty. Starting in 1998 INTLAB is continuously enhanced. The latest Version 14.1 comprises 2083 m-files with more than 76,000 lines of code (with comments more than 137,000). There are several thousand users in more than 50 countries. We describe fundamentals and latest developments in INTLAB including fast and accurate real and complex, full and sparse matrix residuals, sparse linear, in particular nearly symmetric as well as nonlinear systems, and matrix decompositions. Several executable Matlab/Octave codes are included throughout the sections.Publicationtype: Journal Article15 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , On a quality measure for interval inclusionsVerification methods compute intervals which contain the solution of a given problem with mathematical rigour. In order to compare the quality of intervals some measure is desirable. We identify some anticipated properties and propose a method avoiding drawbacks of previous definitions.Publicationtype: Journal Article11 21 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , An Alternative Approach to Probability in Quantum Information ScienceThis chapter provides a probabilistic framework for formulating classical probability theory, quantum probability, thermodynamics, diffusion, and the Wiener integral using a set of four axioms or principles. It explains everything that conventional quantum information theory and classical probability theory achieve. We want to emphasize that this framework is not an interpretation of quantum mechanics such as “Many-Worlds,” “Bohm’s Theory,” or the “Copenhagen interpretation.” It is much more general and can be viewed as a probability algorithm that calculates probabilities of future events. As a result, previously perplexing paradoxes find resolution. In particular, the superposition principle takes on a new meaning. Our probabilistic framework stands apart from the Hilbert space formalism. It relies solely on elementary set theory, classical logic, and complex numbers. Consequently, this theory is accessible for instruction in educational settings. This framework can be regarded as an axiomatic approach to probability in the sense of Hilbert. In his sixth of the twenty-three open problems presented at the International Congress of Mathematicians in Paris in 1900, Hilbert called for an axiomatic probability theory.Publicationtype: Book Part18 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , A note on Oishi’s lower bound for the smallest singular value of linearized Galerkin equationsRecently Oishi published a paper allowing lower bounds for the minimum singular value of coefficient matrices of linearized Galerkin equations, which in turn arise in the computation of periodic solutions of nonlinear delay differential equations with some smooth nonlinearity. The coefficient matrix of linearized Galerkin equations may be large, so the computation of a valid lower bound of the smallest singular value may be costly. Oishi’s method is based on the inverse of a small upper left principal submatrix, and subsequent computations use a Schur complement with small computational cost. In this note some assumptions are removed and the bounds improved. Furthermore a technique is derived to reduce the total computationally cost significantly allowing to treat infinite dimensional matrices.Publicationtype: Journal Article13 14 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Verified error bounds for matrix decompositions(2024); In this note we consider common matrix factorizations such as LU decomposition of a square and rectangular matrix, Cholesky and QR decomposition, singular value decomposition for square and rectangular matrices, and eigen-, Schur, and Takagi decomposition. We first note that well-conditioned factors tend to be sensitive to perturbations of the input matrix, while ill-conditioned factors tend to be insensitive. It seems that this behavior has not been recognized in numerical analysis. We develop a formula for the relation between the condition number of the factor and its sensitivity with respect to input perturbations, and give reasons for that. Our main focus is to describe verification methods for the factors of the mentioned decompositions. That means proving existence of the factorization together with rigorous entrywise error bounds for the factors. Our goal is to develop algorithms requiring \scrO(Pp2) operations for an m \times n matrix with P := max(m,n) and p := min(m,n). Moreover, bounds of high quality are aimed for, often not far from maximal accuracy. A main tool to achieve that is accurate dot products based on error-free transformations. Since preconditioning based on approximate inverses is used, our methods are restricted to full matrices.Publicationtype: Journal Article16 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Fast computation of error bounds for all eigenpairs of a Hermitian and all singular pairs of a rectangular matrix with emphasis on eigen- and singular value clusters(2023-12-15); We present verification methods to compute error bounds for all eigenvectors of a Hermitian matrix as well as for all singular vectors of a rectangular real or complex matrix. In case of clusters these are bounds for an orthonormal basis of the invariant subspace or singular vector space, respectively. Individual error bounds for all eigenvalues and singular values including clustered and/or multiple ones are computed as well. The computed bounds do contain the true result with mathematical certainty, and the algorithms apply to interval data as well. In that case the computed bounds are true for every real/complex matrix within the tolerances. The computational complexity to compute inclusions of all eigen/singular pairs of an n×n matrix or m×n matrix is O(n3) or O(mn2) operations, respectively.Publicationtype: Journal Article47 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , IEEE-754 precision-p base-β Arithmetic Implemented in binaryWe show how an IEEE-754 conformant precision-p base-β arithmetic can be implemented based on some binary floating-point and/or integer arithmetic. This includes the four basic operations and square root subject to the five IEEE-754 rounding modes, namely the nearest roundings with roundTiesToEven and roundTiesToAway, the directed roundings downwards and upwards, as well as rounding towards zero. Exceptional values like ∞ of NaN are covered according to the IEEE-754 arithmetic standard. The results of the precision-p base-β operations are computed using some underlying precision-q binary arithmetic. We distinguish two cases. When using a precision-q binary integer arithmetic, the base-β precision p is limited for all operations by β2p ≤ 2q, whereas using a precision-q binary floating-point arithmetic imposes stronger limits on the base-β precision, namely β2p ≤ 2q for addition and multiplication, β2p ≤ 2q-1 for division and β2p ≤ 2q-3 for the square root. Those limitations cannot be improved. The algorithms are implemented in a Matlab/Octave flbeta-toolbox with the choice of using uint64 or binary64 as underlying arithmetic. The former allows larger precisions, the latter is advantageous for the square root, whereas computing times are similar. The flbeta-toolbox offers precision-p base-β scalar, vector and matrix operations including sparse matrices as well as corresponding interval operations. The base β can be chosen in the range β [2,64]. The flbeta-toolbox will be part of Version 13 of INTLAB [18], the Matlab/Octave toolbox for reliable computing.Publicationtype: Journal Article61 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Fast and accurate computation of the Euclidean norm of a vectorThe numerical computation of the Euclidean norm of a vector is perfectly well conditioned with favorite a priori error estimates. Recently there is interest in computing a faithfully rounded approximation which means that there is no other floating-point number between the computed and the true real result. Hence the result is either the rounded to nearest result or its neighbor. Previous publications guarantee a faithfully rounded result for large dimension, but not the rounded to nearest result. In this note we present several new and fast algorithms producing a faithfully rounded result, as well as the first algorithm to compute the rounded to nearest result. Executable MATLAB codes are included. As a by product, a fast loop-free error-free vector transformation is given. That transforms a vector such that the sum remains unchanged but the condition number of the sum multiplies with the rounding error unit.Publicationtype: Journal Article26 248