# 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](mailto:undefined) of Fractalyze


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://fractalyze.gitbook.io/intro/primitives/abstract-algebra/group/batch-inverse.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.