Reading Notes

Book: "Accuracy and Stability of Numerical Algorithms", Nicholas J. Higham, 2002

Chapter 2: Floating Point Arithmetic

(1) rounding versus chopping: rounding - to the nearest; chopping - to the nearest but satisfy |fl(x)| <= |x|;

(2) Computer chip designs can be tested in two main ways: by software simulations and by applying formal verification techniques. Formal verification aims to prove mathematically that the chip design is correct, and this approach has been in use by chip manufactures for some time.

(3) For most modern computers, it is a rule of thumb that a floating point addition and multiplication take about the same amount of time, while a floating point division is 2-10 times slower, and a square root operation (in hardware) is 1-2 times slower than a division.

(4) In IA-64 architectures, use Newton-based approach to calculate the division. For example, Newton-method for solving $("f(x) = a - \frac{1}{x} = 0")$, then we can get $1/a$ which represents the division operation.

$$x_{k+1} = x_k - \frac{f(x_k)}{f^{'}(x_k)} = x_k - \frac{a-1/x_k}{x^{-2}_k} = x_k + (1 - x_k a)x_k$$

Chapter 9: LU Factorization and Linear Equations

Theorem 9.9(Wilkinson) Let $\pmb{A} \in \mathbb{C}^{n \times n}$ be nonsingular. If $\pmb{A}$ is diagonally dominant by rows or columns then $\pmb{A}$ has a LU factorization without pivoting and the growth factor $\rho_n \leq 2$. If $\pmb{A}$ is diagonally dominant by columns then $|l_{ij}| \leq 1$ for all $i$ and $j$ in the LU factorization without pivoting (hence GEPP does not require any row interchanges).