Greedy and randomized greedy search

Greedy search selects tensor pairs step by step; randomized greedy search generates multiple paths and compares their complete-path objectives.

Greedy search: selecting tensor pairs

Greedy search selects one tensor pair at a time, records the contraction, and replaces the pair with its result. It updates index structure without performing array computation.

The basic local score is:

$C$ is the contraction result, $|\cdot|$ denotes element count, and $\alpha$ corresponds to costmod. Lower scores take priority. This score selects the next step; it is not the complete-path optimization objective.

The following pseudocode omits candidate-set maintenance:

path = []
while there are candidate tensor pairs sharing an index:
    (A, B) = candidate with the lowest local score
    C = compute the contraction result index structure
    Append (A, B) to path
    Replace A and B with C and update candidates
Merge remaining components by outer product in increasing tensor size
return path

A shared index is eliminated in a step only if it is absent from the output and no other tensor still uses it.

Randomized greedy search: comparing trials

random_greedy repeatedly generates complete paths using different parameters. At positive temperature, it also samples with weights from a window of leading candidates, rather than always choosing the top candidate.

Run ntrials attempts in parallel:
    parameters = parameters for this attempt
    path = generate a greedy path using parameters
    score = objective value J(path) of the complete path
return the path with the lowest score

The first three trials, when present, use zero-temperature starts with costmod=1, 4, 8; subsequent trials sample parameters randomly. Trials can run in parallel, but contraction choices within one path remain sequential.

This temperature controls tensor-pair selection; it differs from the temperature used to accept tree changes in simulated annealing.

Interfaces

Randomized greedy search selects candidates using the objective for the current call. In the automatic Light and Heavy pipeline, the top-level interface supplies the objective. Standalone calls use the library default weights unless an objective is specified. See the Rust API for usage. ntrials must be at least 1. Neither greedy nor randomized greedy search guarantees global optimality.

Parallelism

Thread count determines how many trials can run concurrently; it does not automatically increase ntrials. See the Rust API for full parameter and return types.