If you need to multiply k > 1 factors, where m is the size of the resulting factor, the number of multiplications is bounded below by k − 2 + m (as the final product requires m multiplications and each other requires at least one multiplication) and bounded above by (k − 1) ∗ m (as there are k − 1 factor multiplications and each of these requires at most m multiplications).

The associative ordering imposed by absorption into the rules for the variable being eliminated
(which for the example above implies absorbing P(C|B) and P(D|B) into P(B|A)) may not be the optimal multiplication ordering. The absorption ordering (that saves because it reduced splitting)
should be seen as a heuristic; it may be worthwhile to do a meta-level analysis to determine what order to multiply (Bertelè and Brioschi, 1972; Shachter et al., 1990; D'Ambrosio, 1995), but this is beyond the scope of this paper.

## 5.2 Summing Out A Variable

Suppose we are eliminating Y, and we have absorbed all of the confactors that contain Y into the confactors for Y. Then any two confactors in R that contain Y have incompatible contexts. The contexts for the confactors that contain Y in the table are disjoint from the contexts of the confactors that contain Y in the body.

Summing out Y from a confactor that contains Y in the table proceeds as before. We can use a similar trick to absorption to avoid any more splitting when adding confactors that contain Y in the body.

Suppose Y has domain {v1, . . . , vs}. The contexts of the confactors with Y=viin the body are exclusive and the disjunct is logically equivalent to the disjunct of confactors with Y=vjin the body for any other value vj.

For each 1 ≤ i ≤ s, let Ri = {-b, t **: -**b ∧ Y=vi, t ∈ R
+}. Thus Riis the confactor for Y = vi in the context, but with Y = vi omitted from the context. We will combine the Ri's using a binary operation:
R1 ⊕g R2 **= {-**c1 ∪ c2,set(t1, c2) ⊕t set(t2, c1) **: -**c1, t1 ∈ R1,-c2, t2 ∈ R2, *compatible*(c1, c2)}
where ⊕tis an addition operation defined on tables that is identical to the product ⊗t of Definition 3 except that it adds the values instead of multiplying them.

Then R1 ⊕g R2 ⊕g . . . ⊕g Rsis the result from summing out Y from the confactors with Y in the body.

## 5.3 Contextual Variable Elimination With Absorption

A version of *contextual variable elimination* that uses absorption, is given in Figure 9. This is the algorithm used in the experimental results of Section 6.

The elimination procedure is called once for each non-query, non-observed variable. The order in which the variables are selected is called the **elimination ordering**. This algorithm does not imply that the elimination ordering has to be given a priori.

One of the main issues in implementing this algorithm is efficient indexing for the confactors. We want to be able to quickly find the confactors for Y, the confactors that contain Y, and the compatible confactors during addition and absorption. If we are given a prior elimination ordering, we can use the idea of bucket elimination (Dechter, 1996), namely that a confactor can be placed in the bucket of the earliest variable in the elimination ordering. When we eliminate Y, all of the confactors that contain Y are in Y's bucket. If we don't have a prior elimination ordering, we can keep an inverted