PaperlayerView exact revision on arXiv

Source-linked AI summary

The Mode of Null-A: Compositional Computation of a Generalized Inverse

Barak A. Pearlmutter, Jeffrey Mark Siskind

arXiv:2609.38497v1math.NAcs.NAcs.PL

TL;DR

Inverse AD is restricted by invertibility and constant-width assumptions, limiting its use on programs whose active-variable counts change. This paper propagates affine-space preimages compositionally through program Jacobians, including non-square steps. In benchmarks, it is faster than conjugate gradient at nearly every point of the GPT-2 sweep, while the unbatched MLP comparison is more limited.

  • Problem

    Existing inverse-AD methods assume invertible Jacobians and have issues with non-square steps, while many programs change the number of active variables during execution.

    Source: §1 · p. 1, §1.2 · p. 3

  • Method

    The method represents affine spaces with a compositional, quasi-local data structure and propagates their preimages through Jacobian steps, including non-square steps.

    Source: §1 · p. 1, §1.3 · p. 3

  • Results

    Null-A mode preimage AD is 2× to 42× faster than conjugate gradient at every point of the GPT-2 sweep except the largest, and faster only at the smallest and most ill-conditioned points for the unbatched MLP.

    Source: §7 · p. 8

  • Takeaways & Limitations

    The method returns a full preimage rather than a single point, giving problem-specific freedom when selecting among inputs that map into a desired output space.

    Source: §7 · p. 8

    Inverse and preimage AD are not linear operators, making stochastic methods difficult, and the efficiency boundary versus matrix-free methods remains under investigation.

    Source: §10 · p. 9

Abstract

from arXiv · show

We present a novel algorithm for calculating the preimage of an affine space through a product ${J}={J}_{T-1}\cdots{J}_0$ of matrices ${J}_t$ of special form: finding the largest input space $\mathbf{X}$ such that $\mathbf{x}\in\mathbf{X}$ implies ${J}\mathbf{x}\in \mathbf{Y}$, where $\mathbf{Y}$ is a given output affine space. These special matrices arise in AD, where the Jacobians $J$ describing the linearized computation have precisely this structure: the product of a series of linearized primitive numeric operations. This allows us to use the new algorithm to formulate Null-A mode preimage AD, which finds the affine preimage through the Jacobian or Jacobian transpose of a numeric computation. This is a generalization of the inverse AD problem of solving ${J}\acute{\mathbf{x}}^{\ast}=\acute{\mathbf{y}}^{\ast}$ or ${{J}}^{T}\grave{\mathbf{y}}^{\ast}=\grave{\mathbf{x}}^{\ast}$. The key is to represent affine spaces in a fashion which lends itself to efficient preimage calculation, in a compositional and quasi-local fashion, through a succession of matrices ${J}_t$. Unlike previous methods, Null-A preimage mode AD allows the ${J}_t$ matrices to be non-square, corresponding to a computer program whose number of active variables swells and shrinks during the computation. When ${J}$ is square and the initial affine space is a single point, this finds the conventional inverse. But in the more general case, having the entire affine space provides freedom which can be leveraged in a problem-specific manner. We apply the method to small problems on-CPU where the $J_t$ are linearized scalar unary or binary numeric functions; and to larger problems on-GPU where the $J_t$ are linearized aggregate array operations like convolution and attention.

1 INTRODUCTION

The paper generalizes inverse AD to propagate affine-space preimages, addressing the square, invertible-Jacobian assumptions that restrict existing methods. It develops a compositional, quasi-local representation for handling changing program widths.

1 INTRODUCTION

  • Preimage AD generalizes inverse AD by propagating affine sets, extending the approach to programs whose Jacobians may be non-square.This addresses existing inverse-AD methods' assumptions that the Jacobian is invertible and issues with non-square step Jacobians.Source: §1 · p. 1

1.1 AD FORMULATION AND NOTATION

  • A program is a composition of steps whose sparse Jacobians multiply to form the full Jacobian, which can be dense and costly to store.Forward and reverse AD instead use associative Jacobian-vector and vector-Jacobian products.Source: §1.1 · p. 2

1.2 INVERSE AD OF CONSTANT-WIDTH COMPUTATIONS

  • Conventional inverse-Jacobian methods require invertible, square step Jacobians and therefore constant-width computations, while many programs exhibit swell.Aggregating stretches to remove swell can require explicit inversion of large aggregate Jacobians.Source: §1.2 · p. 3

1.3 HANDLING SWELL BY AFFINE-SPACE PROPAGATION

  • Preimage propagation handles non-invertible maps by finding the largest input set mapped into a target set; affine spaces remain closed under linear-map preimages.Preimages compose, so a program's preimage can be calculated stepwise in reverse order; for an invertible map and point target, this reduces to the ordinary inverse.Source: §1.3 · p. 3

1.4 EFFICIENT REPRESENTATION OF AFFINE SPACES

  • For stepwise Jacobians, affine-space preimages can be computed compositionally and quasi-locally despite changes in state size and basis dimension.The representation uses an origin and basis, and the basis may gain sparse columns when taking a preimage through a non-square map.Source: §1.3 · p. 3, §1.4 · p. 4

1.5 AFFINE SPACE SLICES

  • Affine space slices store rows of the origin and basis; lazy queued updates defer nonlocal changes until those slices are accessed.The slice access patterns follow the associated primal values, while basis-column counts can change during preimage computation.Source: §1.5 · p. 4

1.6 NESTING

  • Nested affine space slices allow nested preimage AD, supporting inverse-Hessian-vector products and other combinations of AD operators.The framework uses mechanisms to distinguish cotangents and tangents from different derivative-operator invocations.Source: §1.6 · p. 4

2 MULTIPLICATION OF A STRUCTURALLY-SPARSE MATRIX REPRESENTED AS A GRAPH WITH A DENSE VECTOR

The paper views AD graph traversal as multiplying a structurally sparse matrix by a dense vector, with computations composed from local steps. Linearization supplies the edge operations, while reverse mode reverses the graph and swaps addition with fanout.

  • Tracing can construct the computation graph explicitly, while some forward-mode or source-transformation systems keep it implicit.The primal is evaluated by topologically sorting vertices and applying each noninput vertex's function to its parents' values.Source: §2 · p. 5
  • Linearization makes each vertex compute a dot product of its local gradient with incoming tangent values.Tangent values are multiplied by edge labels, summed at vertices, and passed along outgoing edges.Source: §2 · p. 5
  • Forward mode traverses the linearized graph in primal order; the implementation constructs it explicitly for illustration and traverses it for Jacobian-vector products.The paper says forward mode does not typically require explicit graph construction.Source: §2 · p. 5
  • Reverse-mode vector-Jacobian products reverse edge directions and processing order, swapping addition with fanout.The edge-reversed graph is traversed to compute vector-Jacobian products.Source: §2 · p. 5
  • Graph traversal computes a structurally sparse matrix–dense vector product whose sparsity follows the primal, with computations composed locally.Each step accesses only the cotangent or tangent elements corresponding to the primal step's inputs and outputs.Source: §2 · p. 5

3 THE PREIMAGE OF THE MULTIPLICATION OF A STRUCTURALLY-SPARSE

Preimage AD computes generalized inverse-Jacobian products by propagating affine-space preimages through the graph's linearized operations. Explicit fanout and binary operations make the local preimage steps manageable.

  • Generalized inverse-Jacobian-vector and vector-inverse-Jacobian products are computed as preimages of Jacobian-vector and vector-Jacobian products.Preimage computation makes fanout explicit because its image is a no-op but its preimage is not.Source: §3 · p. 5
  • Explicit fanout splits each linearized vertex into a summing fanin vertex followed by a fanout vertex.Fanout introduction commutes with edge reversal; it supports reverse inverse mode, and together with edge reversal supports forward inverse mode.Source: §3 · p. 5
  • Binarization replaces multi-input additions and multi-output fanouts with binary trees of two-input additions and two-output fanouts.Source: §3 · p. 5
  • The implementation handles binarization implicitly during graph traversal and computes reverse inverse mode by taking preimages of local steps in reverse order.It reverses the order of addition, multiplication, and any needed fanout preimages.Source: §3 · pp. 5–6
  • Forward inverse mode and ordinary reverse mode analogously swap parents with children and reverse the topological processing order.Source: §3 · p. 6

4 THE PREIMAGE OPERATIONS

The preimage operations reduce structured matrix preimage computation to three local maps: constant multiplication, two-input addition, and two-output fanout. The general affine-space formulation motivates lazy handling of their otherwise nonlocal effects.

4 THE PREIMAGE OPERATIONS

  • Only constant multiplication, two-input addition, and two-output fanout require specialized affine-space preimage computations for the graph product.Source: §4 · p. 6

4.1 THE GENERAL CASE

  • An affine space is represented by an origin and basis, and a nonempty preimage is an affine space whose origin maps into the target space.The preimage basis comprises input directions mapped into the target basis span; the origin is obtained by solving Mq = p + Bt.Source: §4.1 · p. 6
  • For arbitrary M, computing the preimage origin and basis is neither compositional nor local, so the method mitigates nonlocality through laziness.Source: §4.1 · p. 6

4.2 THE SPECIAL CASES NEEDED

  • The specialized maps have matrix shapes n×n, n×(n+1), and (n+1)×n; affine-space slices store an origin entry, basis row, and creation timestamp.The timestamp enables delayed nonlocal transformations to be applied when a slice is accessed.Source: §4.2 · p. 7

5 COMPLEXITY

With bounded affine-space dimension, the algorithm's complexity depends on the number of steps and that dimension, rather than requiring explicit Jacobian inversion.

  • O(t²k²) time and O(tk) space suffice; when swell is limited, k is bounded, versus O(n³) time and O(n²) space for explicit Jacobian inversion.Source: §5 · p. 7

7 ARRAY OPERATIONS

The authors implement affine preimage calculations for block primitives and compare Null-A mode preimage AD with conjugate gradient (CG) on MLP and GPT-2 input-matching problems. Null-A is faster across nearly all GPT-2 sweep points, but on the unbatched MLP only at the smallest, most ill-conditioned points.

7 ARRAY OPERATIONS

  • A block primitive with a dense Jacobian needs the general affine-preimage method, but no new mathematics beyond the general linear-map case.The scalar primitives suffice when operations are unary or binary.Source: §7 · p. 7
  • Null-A mode preimage AD is faster than CG across GPT-2 sweep points except the largest, by between 2× and 42×.For the unbatched MLP, it is faster only at the smallest and most ill-conditioned points.Source: §7 · p. 8
  • The benchmark compares Null-A mode preimage AD with CG on MLP and GPT-2 input-matching problems, treating either input data or weights as the input.The GPU implementation uses block (tensor-level) primitives for aggregate array operations.Source: §7 · pp. 7–8

8 RELATED WORK

Prior inverse-AD approaches face restrictions involving invertibility, square Jacobians, swell, or nonlocal computation. The authors position affine-preimage propagation as a compositional alternative and report no prior efficient method for this setting.

8 RELATED WORK

  • General program inversion is described as intractable except in constrained settings, while discrete preimage sets can be represented as streams in PROLOG.Source: §8 · p. 8
  • Earlier linear-system frameworks require noncompositional, nonlocal graph manipulation, while later compositional inverse-AD approaches are limited to constant-width computation.Naumann (2024) groups Jacobian operations into constant-width stretches; Rahimi (2026) targets skinny MLPs.Source: §8 · p. 8
  • Invertible-program methods use carefully constructed architectures and manual inversion, but remain restricted to invertibility.The cited examples include normalizing flows and stable diffusion.Source: §8 · p. 8
  • The authors report no prior efficient propagation of affine spaces to linear preimages or lazy, deferred representations for processing operation sequences.Source: §8 · p. 8

9 DISCUSSION

The discussion presents forward and reverse Null-A preimage AD and describes possible implementation strategies and nested computations. The authors connect nesting to Hessian-vector products, inverse-Hessian-vector products, and Newton steps.

9 DISCUSSION

  • The paper presents forward and reverse Null-A mode preimage AD; its graph-traversal implementations are pedagogical, and reverse mode can trade time for space through checkpointing.The described mutation-based implementation can be made pure by threading the delayed-operation list through A-normal form or continuation-passing style.Source: §9 · pp. 8–9
  • Nesting supports three Hessian-vector-product constructions: forward-over-reverse, reverse-over-forward, and reverse-over-reverse.Source: §9 · p. 9
  • The system also computes inverse-Hessian-vector products in three ways and inverse-Jacobian-vector products of vector-Jacobian products in two ways.Source: §9 · p. 9
  • Null-A mode preimage AD can compute Newton steps by combining either of two inverse-Hessian-vector-product constructions with a vector-Jacobian product.Source: §9 · p. 9

10 LIMITATIONS & FUTURE WORK

Inverse and preimage AD are nonlinear operators, making stochastic methods difficult, and their efficiency relative to matrix-free methods remains under investigation. The current affine-space representation also misses a potential complexity benefit when independent computations yield product spaces.

10 LIMITATIONS & FUTURE WORK

  • Because inverse and preimage AD are not linear operators, the expectation-gradient identity used by stochastic gradient methods does not carry over, making stochastic methods difficult.The efficiency range relative to matrix-free methods used with conventional AD remains to be delineated.Source: §10 · p. 9
  • For parallel functions whose input affine space is a product, the output remains a product, but the current representation does not exploit this structure.The authors suggest that symmetry-aware affine-space representations might reduce complexity.Source: §10 · p. 9

11 CONCLUSION

The paper presents Null-A mode preimage AD as a compositional generalization of inverse AD that accommodates changes in active-variable counts. The conclusion also points to possible uses in nonlinear optimization and machine learning.

11 CONCLUSION

  • Null-A mode preimage AD computes Jacobian and transposed-Jacobian affine-space preimages, including for programs whose active-variable counts increase and decrease.The authors provide a complete Python implementation and describe applications to root finding and inverse-Hessian-vector products for Newton’s Method.Source: §11 · p. 9
  • The authors hope Null-A mode preimage AD may support new machine-learning algorithms, noting that affine spaces lie between point estimates and probability distributions.They also note affine spaces combine well with convex functions and convex optimization.Source: §11 · p. 9

AI USE STATEMENT

  • The AI-use statement says the CPU implementation was hand-coded, while Claude assisted with GPU code and experiment-drafting; authors say they audited the code and approved the final text.The authors state that they directed the core contributions and experimental design and assume responsibility for the content.Source: AI USE STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

  • The reproducibility statement reports a replication package, Tiny Shakespeare experiments, and scripts and environment details for reproducing both implementations.It says the package includes CPU and AI-assisted GPU implementations and is provided in anonymous supplementary material for review.Source: REPRODUCIBILITY STATEMENT · p. 10

ETHICS STATEMENT

  • The ethics statement says the work uses small algorithm benchmarks and a public text dataset, with no human subjects, personal-data tracking, or hazardous applications.The authors report no notable ethical or negative societal concerns.Source: ETHICS STATEMENT · p. 10

A EXAMPLE GRAPH CONSTRUCTIONS

  • The example construction moves from a scalar, control-flow-free program to its primal graph, linearization, reversed edges, explicit fanout, and binarized form.The captions connect the linearized graph to forward-mode Jacobian-vector products and edge reversal to reverse-mode vector-Jacobian products.Source: Figure 2 · p. 13, Figure 3 · p. 13, Figure 4 · p. 14

B THE PREIMAGE OF M×

  • For M× preimages, underconstrained cases use a least-squares solution or add a basis direction, while an inconsistent case has no preimage.The basis-growth operation can be quasi-local, with updates to other slices delayed until access.Source: B THE PREIMAGE OF M× · p. 17

C THE PREIMAGE OF M+

  • For M+ preimages, the basis grows by one and later slices receive a delayed update; the authors note any solution would serve in the stated case.They say optimizing sparsity or representation efficiency would also be reasonable choices.Source: C THE PREIMAGE OF M+ · p. 17

E ON-GPU IMPLEMENTATION OF NULL-A MODE PREIMAGE AD •

The GPU implementation uses block primitives for MLP and GPT-2 benchmarks against a matrix-free conjugate-gradient baseline. Batching is treated separately because it introduces swell.

E ON-GPU IMPLEMENTATION OF NULL-A MODE PREIMAGE AD •

  • The feedforward primitive uses a hand-derived, very wide Jacobian, while the GPT-2 transformer-block primitive obtains a dense Jacobian with torch.func.jacrev over activations and twelve parameter tensors.A block primitive needs a way to obtain a dense Jacobian; the authors note that adding one has low cost.Source: E ON-GPU IMPLEMENTATION OF NULL-A MODE… · p. 19
  • The implementation runs in PyTorch on a Dell GB10 GPU, and its block implementations were checked against scalar implementations.Source: E ON-GPU IMPLEMENTATION OF NULL-A MODE… · p. 19

E.1 COMPARISON AGAINST CG AT SCALE

  • The benchmarks compare Null-A preimage AD with matrix-free CG on MLPs and GPT-2, with and without batching, to examine when each method performs better.The CG baseline uses torch.func.jvp and torch.func.vjp without constructing J and returns the minimum-ℓ2-norm point.Source: §E.1 · p. 19
  • Batching is evaluated separately because it introduces swell, as active dimensions can expand and contract during computation.The text notes that standard deep-learning models are generally not constant-width.Source: §E.1 · p. 19

F ON-GPU BENCHMARKS OF NULL-A MODE PREIMAGE AD vs. CG

The on-GPU benchmarks show that the faster method depends on conditioning, output width, model, and batching. Null-A can also return a usable preimage where CG fails in a tested case.

F ON-GPU BENCHMARKS OF NULL-A MODE PREIMAGE AD vs. CG

G NON-ℓ2 SELECTION OVER THE AFFINE SPACE

The section demonstrates how an affine preimage can support selecting an input perturbation under a criterion, rather than returning only one inverse point. In the GPT-2 example, an ℓ1-based selection reaches the target output, unlike the CG-derived ℓ2 choice.

G NON-ℓ2 SELECTION OVER THE AFFINE SPACE

  • The GPT-2 example searches the affine preimage of input-embedding perturbations for a prompt changing only two characters to elicit a target output.The preimage is selected using linear programming and then searched over the chosen positions.Source: G NON-ℓ2 SELECTION OVER THE AFFINE SPACE · p. 22
  • ℓ1 favors perturbations concentrated on few token positions, while the minimum-ℓ2 point spreads perturbation across positions and typically ranks the wrong characters highest.ℓ1 is described as a convex approximation to ℓ0, which would give the smallest support but is NP-hard.Source: G NON-ℓ2 SELECTION OVER THE AFFINE SPACE · p. 22
  • The example is a proof of concept, not a benchmark; the authors note that searching a small preimage can be faster than searching a huge problem space in appropriate circumstances.Source: G NON-ℓ2 SELECTION OVER THE AFFINE SPACE · p. 22

H NUMERICAL STABILITY IN DEEP COMPUTATIONS

This section examines problem-dependent numerical stability in Null-A computations and presents Python routines for derivative accumulation and affine-space preimage propagation through computation graphs. The routines cover scalar and binary operations, as well as dense or sparse affine-space operations, while noting that block primitives are reported as more robust and that scalar decisions and near-parallel basis elements can pose difficulties.

H NUMERICAL STABILITY IN DEEP COMPUTATIONS

  • Null-A avoids orthogonalization-specific errors by not orthogonalizing its basis, but near-parallel basis elements can still cause errors.Source: H NUMERICAL STABILITY IN DEEP… · p. 23
  • A highly batched, deep, narrow MLP at initialization can yield a noisy origin estimate but not a noisy basis estimate; GPT-2 does not show this issue.The MLP behavior is attributed to near dependence among Jacobian rows for different samples; stability is described as highly problem-dependent.Source: H NUMERICAL STABILITY IN DEEP… · p. 23
  • Block primitives are more robust than scalar decisions, using each layer’s largest Jacobian pivot to decide rank and remaining correct up to cond(J) = 1.5 × 1013.Scalar preimage AD makes about 105 independent zero/nonzero decisions, which cannot be made correctly in isolation because a scalar multiply gives no information about whether its coefficient is meaningful.Source: H NUMERICAL STABILITY IN DEEP… · p. 23

K PYTHON CODE TO PERFORM EDGE REVERSAL

L PYTHON CODE TO PERFORM FORWARD MODE

M PYTHON CODE TO PERFORM REVERSE MODE

N PYTHON CODE TO PERFORM REVERSE NULL-A MODE PREIMAGE AD

O PYTHON CODE TO PERFORM FORWARD NULL-A MODE PREIMAGE AD

P PYTHON CODE FOR HESSIAN-VECTOR PRODUCTS AND NEWTON STEPS

Q PYTHON CODE FOR DENSE LINEAR-ALGEBRA COMPUTATIONS; R PYTHON CODE FOR SPARSE LINEAR-ALGEBRA COMPUTATIONS

S PYTHON CODE FOR COMPUTING PREIMAGES OF AFFINE SPACE SLICES

  • Affine-space slice code stores origins and bases and applies constrained or unconstrained growth operations, with dense or sparse backend selection.Source: S PYTHON CODE FOR COMPUTING PREIMAGES… · p. 32
  • Pending operations from a slice’s timestamp are applied successively to its origin and basis before returning an updated affine slice.The helper initializes from Y.origin and Y.basis, then applies each delayed operation in order.Source: S PYTHON CODE FOR COMPUTING PREIMAGES… · p. 32
  • For nonzero scalar multiplication, the routine divides the slice’s origin and basis by the scalar to form the preimage.It first applies any pending operations to the slice.Source: S PYTHON CODE FOR COMPUTING PREIMAGES… · p. 32
  • For multiplication by zero, nonzero(a) triggers a constrained grow and returns origin 0 with basis e1(Y.basis); when Y.origin is nonzero, the routine raises an empty-preimage error.In the remaining else branch, it records an unconstrained grow and returns Y.origin with cons_one(Y.basis).Source: S PYTHON CODE FOR COMPUTING PREIMAGES… · pp. 32–33
  • Binary addition records an unconstrained grow and returns two slices, using the output basis with signs −1 and e1.Source: S PYTHON CODE FOR COMPUTING PREIMAGES… · p. 33
  • For fanout with differing bases, the routine computes their difference and a scalar offset, records a shrink, and returns a reduced affine slice.The returned basis drops the selected coordinate after subtracting a scaled basis difference.Source: S PYTHON CODE FOR COMPUTING PREIMAGES… · p. 33
  • For fanout with equal bases, differing origins raise an empty-preimage error; otherwise the routine raises if the basis is nonzero and returns the origin if it is zero.Source: S PYTHON CODE FOR COMPUTING PREIMAGES… · p. 33

T PYTHON CODE FOR A BENCHMARK TO TEST THE ASYMPTOTIC COMPLEXITY SCALING OF §5

The benchmark sweeps step count, swell, and input/output dimension, comparing the implementation with an explicit inverse-Jacobian-vector product. It checks output agreement and records function-call counts and runtime.

T PYTHON CODE FOR A BENCHMARK TO TEST THE ASYMPTOTIC COMPLEXITY SCALING OF §5

  • Its constructed program creates swell by copying an intermediate value k times, then applies h across the input values.The current f, g, and h are contrived to make the overall function the identity, so its Jacobian is trivially invertible.Source: T PYTHON CODE FOR A BENCHMARK TO TEST… · p. 34
  • The benchmark varies t, k, and n from 1 to 10, with t scaled by 3 and k scaled by 3 in each run.The code comments identify t with step count, k with swell, and n with input/output dimension.Source: T PYTHON CODE FOR A BENCHMARK TO TEST… · p. 34
  • The script compares `ijvp` with an explicit inverse-Jacobian-vector product, checks that their outputs match exactly, and records calls and runtime.It raises an error if the output difference has nonzero norm.Source: T PYTHON CODE FOR A BENCHMARK TO TEST… · pp. 34–35

U COMPUTATION GRAPH FOR THE BENCHMARK IN §T

Figure 8 depicts the primal floating-point computation graph for the benchmark program in §T.

U COMPUTATION GRAPH FOR THE BENCHMARK IN §T

  • Figure 8 shows the primal floating-point computation graph corresponding to the program in §T.The caption does not specify graph encodings or comparisons.Source: Figure 8 · p. 36

V OUTPUT OF THE BENCHMARK THAT DEMONSTRATES THE ASYMPTOTIC COMPLEXITY SCALING OF §5

The benchmark reports call counts and runtimes for two methods across settings of t, k, and n to characterize their scaling as n grows.

V OUTPUT OF THE BENCHMARK THAT DEMONSTRATES THE ASYMPTOTIC COMPLEXITY SCALING OF §5

  • For t=5,k=2, as n rises from 3 to 10, our calls increase from 1065 to 3585 while their calls rise from 9585 to 107550.The call-count increase is substantially steeper for their implementation in this parameter setting.Source: V OUTPUT OF THE BENCHMARK THAT… · p. 54
  • At t=5,k=10, our time is 1.298192 versus their time of 0.453135 at n=1, but 13.692086 versus 387.176759 at n=10.The reported timing comparison changes with n for this setting.Source: V OUTPUT OF THE BENCHMARK THAT… · p. 57
  • At t=8,k=10,n=10, our calls are 23016 versus their 690480, and our time is 24.089433 versus their 732.795608.This record extends the comparison to a larger t setting.Source: V OUTPUT OF THE BENCHMARK THAT… · p. 69
Loading 2609.38497v1…