vp.randla.trace_hutchpp

Hutch++'s trace estimate from m products.

Part of the distribution vipyr; it runs from a checkout of the repository. Planned on PyPI as pip install vipyr.

Signature

vp.randla.trace_hutchpp(A, m, seed)

Parameters

A : ndarray[float64], required

m : int, required

seed : int, required

Returns

A frozen TraceHutchppResult. Iterating it gives the fields below in order; it also has params, tests, log and check().

trace : float

The estimate of the trace of A.

Raises

TypeError

An argument of the wrong type, or an unknown keyword.

vipyr.VivBuildError

An ImportError: no C compiler, or the program's C does not build.

Examples

import numpy as np
import vipyr as vp
rng = np.random.default_rng(0)
Q, _ = np.linalg.qr(rng.standard_normal((200, 200)))
lam = np.arange(1, 201) ** -2.0
r = vp.randla.trace_hutchpp(A=(Q * lam) @ Q.T, m=48, seed=0)
print(r.trace, lam.sum())                 # the estimate and the exact trace
assert r.check()

1.6376920108478306 1.6399465460149976

Each example ran as written when these pages were generated, and the output shown is what it printed.

Checked against

Reference

lib/randla/check_ref.py: on a 400 by 400 matrix with eigenvalues j^-2, the mean relative error over 8 seeds falls with the number of products m with a fitted slope above 0.9 (Hutchinson's falls as m^-1/2).

Source

• Viv: lib/randla/api.viv
• The defs it reaches and the calls between them: map of the code