# Batch Inverse

## **What is Batch Inverse?**

**Batch Inverse** is a technique used to efficiently compute the inverses of multiple values $$(v\_1, \dots, v\_n)$$ at once. Normally, calculating each inverse separately requires $$n \times \mathsf{INV}$$ (inverse operations), but with Batch Inversion, you can compute all the inverses using **just a single inverse operation**.

As inverse operations are significantly more expensive than multiplications, this method is especially useful in performance-sensitive contexts—such as in ZK provers.

***

## **How Does It Work?**

Let’s walk through an example of computing the inverses of four values: $$(a, b, c, d)$$

### 1. Compute Prefix Products

Multiply the values one by one, keeping track of intermediate results:

* $$P\_1 = a$$
* $$P\_2 = ab$$
* $$P\_3 = abc$$
* $$P\_4 = abcd$$

So we get:

$$
P = (P\_1, P\_2, P\_3, P\_4)
$$

### 2. Compute Inverse of the Final Product

Compute the inverse of the final product:

$$
t = P\_4^{-1} = (abcd)^{-1}
$$

This is the **only inverse operation** required.

### 3. Compute Each Inverse in Reverse

Now, traverse the values in reverse to compute individual inverses:

* $$d^{-1} = P\_3 \times t$$, then update $$t = t \times d = (abc)^{-1}$$
* $$c^{-1} = P\_2 \times t$$, then update $$t = t \times c = (ab)^{-1}$$
* $$b^{-1} = P\_1 \times t$$, then update $$t = t \times b = (a)^{-1}$$
* $$a^{-1} = t$$

This phase involves only **multiplication operations**.

***

## **Computational Complexity**

If the vector has length $$n$$, the total computational cost is:

1. **Prefix Product Computation**: $$(n - 1) \times \mathsf{MUL}$$
2. **One Inverse Operation**: $$1 \times \mathsf{INV}$$
3. **Reverse Traversal**: $$2(n - 1) \times \mathsf{MUL}$$

**Total:**

$$
3(n - 1) \times \mathsf{MUL} + 1 \times \mathsf{INV}
$$

> Written by [Ryan Kim](https://app.gitbook.com/u/cPk8gft4tSd0Obi6ARBfoQ16SqG2 "mention") of Fractalyze