# Sum-Product Algorithms¶

`partial_sum_product`(sum_op, prod_op, factors, eliminate=frozenset(), plates=frozenset())[source]

Performs partial sum-product contraction of a collection of factors.

Returns: a list of partially contracted Funsors. list
`sum_product`(sum_op, prod_op, factors, eliminate=frozenset(), plates=frozenset())[source]

Performs sum-product contraction of a collection of factors.

Returns: a single contracted Funsor. `Funsor`
`naive_sequential_sum_product`(sum_op, prod_op, trans, time, step)[source]
`sequential_sum_product`(sum_op, prod_op, trans, time, step)[source]

For a funsor `trans` with dimensions `time`, `prev` and `curr`, computes a recursion equivalent to:

```tail_time = 1 + arange("time", trans.inputs["time"].size - 1)
tail = sequential_sum_product(sum_op, prod_op,
trans(time=tail_time),
time, {"prev": "curr"})
return prod_op(trans(time=0)(curr="drop"), tail(prev="drop"))            .reduce(sum_op, "drop")
```

but does so efficiently in parallel in O(log(time)).

Parameters: sum_op (AssociativeOp) – A semiring sum operation. prod_op (AssociativeOp) – A semiring product operation. trans (Funsor) – A transition funsor. time (Variable) – The time input dimension. step (dict) – A dict mapping previous variables to current variables. This can contain multiple pairs of prev->curr variable names.
`mixed_sequential_sum_product`(sum_op, prod_op, trans, time, step, num_segments=None)[source]

For a funsor `trans` with dimensions `time`, `prev` and `curr`, computes a recursion equivalent to:

```tail_time = 1 + arange("time", trans.inputs["time"].size - 1)
tail = sequential_sum_product(sum_op, prod_op,
trans(time=tail_time),
time, {"prev": "curr"})
return prod_op(trans(time=0)(curr="drop"), tail(prev="drop"))            .reduce(sum_op, "drop")
```

by mixing parallel and serial scan algorithms over `num_segments` segments.

Parameters: sum_op (AssociativeOp) – A semiring sum operation. prod_op (AssociativeOp) – A semiring product operation. trans (Funsor) – A transition funsor. time (Variable) – The time input dimension. step (dict) – A dict mapping previous variables to current variables. This can contain multiple pairs of prev->curr variable names. num_segments (int) – number of segments for the first stage
`naive_sarkka_bilmes_product`(sum_op, prod_op, trans, time_var, global_vars=frozenset())[source]
`sarkka_bilmes_product`(sum_op, prod_op, trans, time_var, global_vars=frozenset(), num_periods=1)[source]
class `MarkovProductMeta`(name, bases, dct)[source]

Bases: `funsor.terms.FunsorMeta`

Wrapper to convert `step` to a tuple and fill in default `step_names`.

class `MarkovProduct`(sum_op, prod_op, trans, time, step, step_names)[source]

Lazy representation of `sequential_sum_product()` .

Parameters: sum_op (AssociativeOp) – A marginalization op. prod_op (AssociativeOp) – A Bayesian fusion op. trans (Funsor) – A sequence of transition factors, usually varying along the `time` input. time (str or Variable) – A time dimension. step (dict) – A str-to-str mapping of “previous” inputs of `trans` to “current” inputs of `trans`. step_names (dict) – Optional, for internal use by alpha conversion.
`eager_subs`(subs)[source]
`eager_markov_product`(sum_op, prod_op, trans, time, step, step_names)[source]