Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
8,509
result(s) for
"Computer arithmetic."
Sort by:
Improved Error Bounds for Inner Products in Floating-Point Arithmetic
Given two floating-point vectors $x,y$ of dimension $n$ and assuming rounding to nearest, we show that if no underflow or overflow occurs, any evaluation order for an inner product returns a floating-point number ${\\widehat r}$ such that $|{\\widehat r}- x^Ty| \\leqslant nu|x|^T|y|$ with $u$ the unit roundoff. This result, which holds for any radix and with no restriction on $n$, can be seen as a generalization of a similar bound given in [S. M. Rump, BIT, 52 (2012), pp. 201--220] for recursive summation in radix $2$, namely, $|{\\widehat r}- x^Te| \\leqslant (n-1)u|x|^Te$ with $e=[1,1,\\ldots,1]^T$. As a direct consequence, the error bound for the floating-point approximation $\\widehat{C}$ of classical matrix multiplication with inner dimension $n$ simplifies to $|\\widehat{C}-AB|\\leqslant nu|A||B|$. [PUBLICATION ABSTRACT]
Journal Article
Improved Backward Error Bounds for LU and Cholesky Factorizations
Assuming standard floating-point arithmetic (in base $\\beta$, precision $p$) and barring underflow and overflow, classical rounding error analysis of the LU or Cholesky factorization of an $n\\times n$ matrix $A$ provides backward error bounds of the form $|\\Delta A| \\le \\gamma_n |\\widehat L| |\\widehat U|$ or $|\\Delta A| \\le \\gamma_{n+1} |\\widehat R^T| |\\widehat R|$. Here, $\\widehat L$, $\\widehat U$, and $\\widehat R$ denote the computed factors, and $\\gamma_n$ is the usual fraction $nu/(1-nu) = nu + {\\mathcal O}(u^2)$ with $u$ the unit roundoff. Similarly, when solving an $n\\times n$ triangular system $Tx = b$ by substitution, the computed solution $\\widehat x$ satisfies $(T+\\Delta T)\\widehat x = b$ with $|\\Delta T| \\le \\gamma_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 $\\gamma_n$ and $\\gamma_{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 $|\\rho-s|$, where $s$ is the exact sum of a floating-point number and $n-1$ real numbers and where $\\rho$ is a real number approximating the computed sum $\\widehat s$. By instantiating this framework with suitable values of $\\rho$, 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. [PUBLICATION ABSTRACT]
Journal Article
Entangling logical qubits with lattice surgery
The development of quantum computing architectures from early designs and current noisy devices to fully fledged quantum computers hinges on achieving fault tolerance using quantum error correction
1
–
4
. However, these correction capabilities come with an overhead for performing the necessary fault-tolerant logical operations on logical qubits (qubits that are encoded in ensembles of physical qubits and protected by error-correction codes)
5
–
8
. One of the most resource-efficient ways to implement logical operations is lattice surgery
9
–
11
, where groups of physical qubits, arranged on lattices, can be merged and split to realize entangling gates and teleport logical information. Here we report the experimental realization of lattice surgery between two qubits protected via a topological error-correction code in a ten-qubit ion-trap quantum information processor. In this system, we can carry out the necessary quantum non-demolition measurements through a series of local and entangling gates, as well as measurements on auxiliary qubits. In particular, we demonstrate entanglement between two logical qubits and we implement logical state teleportation between them. The demonstration of these operations—fundamental building blocks for quantum computation—through lattice surgery represents a step towards the efficient realization of fault-tolerant quantum computation.
Two logical qubits are encoded in ensembles of four physical qubits through the surface code, then entangled by lattice surgery, which is a protocol for carrying out fault-tolerant operations.
Journal Article
Computer Arithmetic and Validity
The series de Gruyter Studies in Mathematics was founded in 1982 by the late Professor Heinz Bauer and Professor Peter Gabriel. The series publishes monographs and textbooks in mathematics and its applications. Apart from covering important areas of current interest, a major aim is to make topics of an interdisciplinary nature accessible to the non-specialist. Each volume undergoes peer review using a double-blind reviewing process.
eBook
Floating-point arithmetic
Floating-point numbers have an intuitive meaning when it comes to physics-based numerical computations, and they have thus become the most common way of approximating real numbers in computers. The IEEE-754 Standard has played a large part in making floating-point arithmetic ubiquitous today, by specifying its semantics in a strict yet useful way as early as 1985. In particular, floating-point operations should be performed as if their results were first computed with an infinite precision and then rounded to the target format. A consequence is that floating-point arithmetic satisfies the ‘standard model’ that is often used for analysing the accuracy of floating-point algorithms. But that is only scraping the surface, and floating-point arithmetic offers much more. In this survey we recall the history of floating-point arithmetic as well as its specification mandated by the IEEE-754 Standard. We also recall what properties it entails and what every programmer should know when designing a floating-point algorithm. We provide various basic blocks that can be implemented with floating-point arithmetic. In particular, one can actually compute the rounding error caused by some floating-point operations, which paves the way to designing more accurate algorithms. More generally, properties of floating-point arithmetic make it possible to extend the accuracy of computations beyond working precision.
Journal Article
Arithmetic and logic in computer systems
The book describes the fundamental principles of computer arithmetic. Algorithms for performing operations like addition, subtraction, multiplication and division in digit computer systems are presented, with the goal of explaining the concepts behind the algorithms, rather than addressing any direct applications.
eBook
The exact dot product as basic tool for long interval arithmetic
Computing with guarantees is based on two arithmetical features. One is fixed (double) precision interval arithmetic. The other one is dynamic precision interval arithmetic, here also called long interval arithmetic. The basic tool to achieve high speed dynamic precision arithmetic for real and interval data is an exact multiply and accumulate operation and with it an exact dot product. Pipelining allows to compute it at the same high speed as vector operations on conventional vector processors. Long interval arithmetic fully benefits from such high speed. Exactitude brings very high accuracy, and thereby stability into computation. This document, which has been incorporated into the draft standard for interval arithmetic being developed by IEEE P1788, specifies the implementation of an exact multiply and accumulate operation.
Journal Article
Five-Precision GMRES-Based Iterative Refinement
GMRES-based iterative refinement in three precisions (GMRES-IR3) uses a low precision LU factorization to accelerate the solution of a linear system without compromising numerical stability or robustness. GMRES-IR3 solves the update equation using GMRES preconditioned by the LU factors, where all operations within GMRES are carried out in the working precision u, except for the matrix-vector products and the application of the preconditioner, which require the use of extra precision u 2. The use of extra precision can be expensive, and is especially unattractive if it is not available in hardware; for this reason, existing implementations have not used extra precision, despite the absence of an error analysis for this approach. We relax the requirements on the precisions used within GMRES, allowing the use of arbitrary precisions up (for applying the preconditioner) and ug (for the rest of the operations). We obtain the five-precision GMRES-based iterative refinement (GMRES-IR5) algorithm. We carry out a rounding error analysis that generalizes that of GMRES-IR3, obtaining conditions under which the forward and backward errors converge to their limiting values. Our analysis makes use of a new result on the backward stability of MGS-GMRES in two precisions. On hardware where up to five arithmetics are available, the number of possible combinations of precisions in GMRES-IR5 is extremely large, but our analysis identifies a small subset of relevant combinations. By choosing from within this subset one can achieve different levels of tradeoff between cost and robustness, which allows for a finer choice of precisions depending on the problem difficulty and the available hardware. Our numerical experiments on both random dense matrices and real-life sparse matrices from a wide range of applications show that the practical behavior of GMRES-IR5 is in good agreement with our theoretical analysis. GMRES-IR5 therefore has the potential to solve relatively badly conditioned problems in less time and memory than GMRES-IR3, thanks to the use of lower precision arithmetic in the GMRES iterations.
Journal Article
Digital Curricula in School Mathematics
The mathematics curriculum is influenced by digital technology in delivery and practice. This volume, from a 2014 University of Chicago conference, explores changes in curricular materials, student learning, and teacher roles. Experts discuss how technology impacts math education, challenging traditional paper-and-pencil methods.
eBook