Ill-Conditioned Sums and Dot Products
mtl::generators::gen_dot and mtl::generators::gen_sum build vectors whose dot product or sum has a chosen condition number, up to hundreds of bits of cancellation. They are the test-data generators of Ogita, Rump and Oishi, “Accurate sum and dot product”, SIAM J. Sci. Comput. 26(6), 2005, Section 6. They are what MTL5 uses to measure its accumulation configurations and its K-fold algorithms against the paper.
Header: include/mtl/generators/ill_conditioned.hpp (also pulled in by mtl/generators/generators.hpp and mtl/mtl.hpp).
#include <mtl/generators/ill_conditioned.hpp>
auto d = mtl::generators::gen_dot<double>(100, 1e30, std::uint64_t{42});// d.x, d.y: dense_vector<double> of length 100// d.d: x . y, rounded to nearest// d.cond: the achieved condition number, 2 |x|.|y| / |x.y|
auto s = mtl::generators::gen_sum<double>(200, 1e30, std::uint64_t{42});// s.p: dense_vector<double> of length 200// s.s: sum p, rounded to nearest// s.cond: the achieved condition number, sum |p_i| / |sum p_i|Each generator has two overloads: one takes a seed, and the other takes a std::mt19937_64& so that a battery can draw a sequence of instances from one stream.
The condition numbers
Section titled “The condition numbers”The paper defines the condition number of a dot product in (5.7) and that of a sum in (4.9):
| condition number | ||
|---|---|---|
| dot product | `cond(xᵀy) = 2· | x |
| sum | `cond(Σpᵢ) = Σ | pᵢ |
The error bounds of every algorithm in Error-Free Transformations are in terms of these. Both generators report the achieved condition number, computed exactly, and the paper plots its errors against that value rather than the anticipated one.
gen_dot: GenDot (Algorithm 6.1)
Section titled “gen_dot: GenDot (Algorithm 6.1)”For a length n ≥ 6 and an anticipated condition number c, with b = log2(c) and n2 = round(n/2):
- First half.
x(i)andy(i)are random in(−1, 1)·2^e, with exponentsedrawn from0..b/2. The first exponent is set toround(b/2) + 1and the last to 0, so that both ends of the range occur. - Second half. The exponents fall linearly from
b/2to 0. Eachx(i)is random at that exponent.y(i)is chosen so that the exact running dot product is cancelled down to a random value at that exponent:y(i) = (r·2^e − DotExact(x, y)) / x(i). - Permute.
xandyare permuted together.
This follows the paper’s Matlab code step by step. The only external routine it needs is DotExact, “a floating point number r ∈ F near to the exact value of the dot product”. MTL5 uses math::exact_accumulator, which computes the exact sum and rounds it once to nearest. So no substitute is involved, and the generator is defined for the types the exact accumulator covers: float and double.
How close the achieved condition number is. As the paper reports in Table 6.1, the achieved condition number is typically about 10× the anticipated one, with a wide spread. This is the ratio of achieved to anticipated over 500 draws with n = 100..500:
| min | median | max | range of c | |
|---|---|---|---|---|
| MTL5, double | 0.020 | 11.2 | 4.9e3 | 1 .. 1e100 |
| MTL5, float | 0.38 | 15.7 | 3.7e3 | 1 .. 1e30 |
| paper, Table 6.1 | 1.5e-3 | 10.0 | 1.9e6 | 1 .. 1e100, 50 000 draws |
gen_sum: the paper’s ill-conditioned sums
Section titled “gen_sum: the paper’s ill-conditioned sums”The paper builds an ill-conditioned sum of length 2m from a dot product of length m: “using Algorithm 3.3 (TwoProduct) and randomly permuting the summands”. gen_sum(n, c) does the following for an even n ≥ 12:
- It draws
gen_dot(n/2, c). - It splits each product
x(i)·y(i)exactly intohi + lowithmath::two_product. - It permutes the
nsummands.
The exact sum is therefore x·y, and Σ|pᵢ| equals |x|ᵀ|y| to within the rounding of the hi parts. The sum’s condition number is consequently half the dot product’s.
Range and portability
Section titled “Range and portability”- Range. The entries reach
2^(b/2 + 1)and the products2^(b + 2), socmust stay below about2^(max_exponent − 4): about 2e37 infloatand 1e307 indouble. This is asserted. - Portable draws. Every random number is taken from the raw
std::mt19937_64stream. The standard specifies that stream bit for bit; it does not specify<random>’s distributions, whose output differs between standard libraries. So a seed gives the same vectors with every compiler and standard library. The paper’srandis uniform on (0, 1); here it is a 53-bit uniform on [0, 1). - Arithmetic. The construction uses
Tarithmetic: forfloat, the cancellation step is done infloat. The paper works in double only.
Testing
Section titled “Testing”tests/unit/generators/test_ill_conditioned.cpp checks:
- reproducibility from a seed;
- that
dis the exact dot product rounded to nearest; - that
condis the exact (5.7); - that the median achieved-to-anticipated ratio lies within [1, 100];
- that
gen_sum’s summands add up exactly to the GenDot product drawn from the same seed, with half its condition number.
The [586:dot], [586:gemm] and [586:determinism] batteries in tests/unit/operation/test_accumulation_configs_mt.cpp draw their data from gen_dot.
Related
Section titled “Related”- Error-Free Transformations:
two_sum,two_product, the compensated accumulator,sum_kanddot_k, and their bounds - Exact Accumulator: the
DotExactbehind GenDot - Accurate Sum and Dot Product: the paper’s Section 6 experiments, run on this data
- #611: reproducing Ogita, Rump and Oishi