Skip to content

Latest commit

 

History

History
67 lines (59 loc) · 4.83 KB

README.md

File metadata and controls

67 lines (59 loc) · 4.83 KB

multidouble for Python

Double-double arithmetic on numpy arrays, backed by the Rust crate multidouble. A double-double array is a pair of float64 arrays (hi, lo) whose elementwise sum hi + lo carries about 32 significant digits.

import numpy as np
import multidouble as md

ah, al = np.array([1.0, 2.0]), np.zeros(2)
bh, bl = np.array([3.0, 3.0]), np.zeros(2)
qh, ql = md.div(ah, al, bh, bl)          # 1/3 and 2/3 to about 32 digits
xh, xl = md.dd_solve(np.eye(2) * 2, np.zeros((2, 2)), qh, ql)
print(md.isa())                           # the SIMD backend in use, detected at run time
  • add, sub, mul, div(ah, al, bh, bl): elementwise, any length, 8 lanes at a time on the best SIMD backend the CPU has (AVX-512, AVX2, SSE2, NEON or plain), bitwise the same results on every backend; dd_op(op, ...) with op 0 add, 1 mul, 2 div, 3 sub.
  • dd_dot(xh, xl, yh, yl): a dot product in double-double, 8 lanes at a time and then the lane sums, to about (n / 8 + 12) 2^-106 of sum |x_i y_i|; returns (hi, lo) as floats.
  • dd_matvec(Ah, Al, vh, vl): A v in double-double, A as (n, m) row-major hi and lo arrays, each row of the result a dd_dot.
  • dd_horner(ch, cl, a): sum_k c_k a^k by Horner's rule in double-double at a float a, the coefficients c_0, ..., c_N as sequences of N + 1 hi and lo arrays of one length n or as (N + 1, n) arrays, each step dd_add(c_k, dd_scale(p, a)) bit for bit, 8 values at a time; returns the (hi, lo) arrays of the n sums. Float64 powers a**k would carry about 2^-53 of each term unless a is a power of two.
  • dd_solve(Ah, Al, bh, bl): x with A x = b by LU with partial pivoting, A as (n, n) row-major hi and lo arrays.
  • qd_solve(a0, a1, a2, a3, b0, b1, b2, b3): x with A x = b by LU with partial pivoting in quad-double, A as four (n, n) part arrays and b as four part arrays of shape (n,) or (n, k) (k right-hand sides), each entry the exact sum of its parts in any order; returns the four parts of x, of b's shape, to about cond(A) 2^-209. QDLu(a0, a1, a2, a3) factors A once, and its solve(b0, b1, b2, b3, transpose=False) gives the bits of qd_solve (or solves A^T x = b) without factoring again. Both raise ValueError for a singular A and for entries that are not finite.
  • qd_add_dd(z0, z1, z2, z3, dh, dl): a quad-double array (four float64 arrays, each element the exact sum of its parts in any order) plus a double-double one, elementwise in quad-double; returns the four parts of the sum.
  • qd_axpy(a, x0, x1, x2, x3, y0, y1, y2, y3): y + a x for quad-double arrays x and y (normalized parts) and a float a, elementwise in quad-double; returns the four parts.
  • od_solve(a0, ..., a7, b0, ..., b7): x with A x = b by LU with partial pivoting in octo-double (eight parts, about 126 digits), A as eight (n, n) part arrays and b as eight of shape (n,) or (n, k), each entry the exact sum of its parts in any order; returns the eight parts of x, to about cond(A) 2^-418. ODLu(a0, ..., a7) keeps the factors for several solves, solve(b0, ..., b7, transpose=False).
  • od_add_dd(z0, ..., z7, dh, dl): an octo-double array (eight float64 arrays, each element the exact sum of its parts in any order) plus a double-double one, elementwise in octo-double; returns the eight parts of the sum.
  • od_axpy(a, x0, ..., x7, y0, ..., y7): y + a x for octo-double arrays x and y (normalized parts) and a float a, elementwise in octo-double; returns the eight parts.
  • The array arguments of the functions above may be any arrays or sequences of real numbers, strided, in Fortran order or of another numeric dtype. Each is converted to a C-contiguous float64 array (np.ascontiguousarray), and one that is already so is passed on without a copy. Complex, string, None and masked inputs raise TypeError.
  • In numpy (plain float64 expressions): two_sum, two_prod (Dekker), dd_add, dd_scale (times an f64), dd_axpy (y + a x), dd_norm (max |hi + lo|), dd_from_mp (from mpmath numbers; needs mpmath).
  • gcr(apply, precond, bh, bl): x with A x = b in double-double by right-preconditioned GMRES in its GCR form, given apply(uh, ul), the product A u in double-double, and precond(rh, rl), an approximate solve such as an f64 LU of A: the refinement of a mixed-precision solve to double-double accuracy (coef="f64" keeps the coefficients in float64, which is cheaper and stalls near float64 accuracy, enough inside a Newton iteration).

Build and test

Needs a Rust toolchain (1.89 or later).

pip install ./python                    # from the repository root, builds with maturin
pip install pytest mpmath && pytest python/tests

The tests compare every operation with exact rational arithmetic (fractions.Fraction) or with mpmath at more digits than the result holds, and contain controls that feed the same checks a wrong result.