# Faster Gaussian Elimination

Last time we saw how to solve $Ax = b$ with a complexity of $O(n^{4}(\log n + b))$. We now want to see if we can solve the same question with $O(n^{3})$ complexity.

Consider solving $Ax = b\ (mod\ p)$ where $p$ is a prime. We can still use Gaussian Elimination and, without loss of generality, assume that $a_{ij} \in \{0, \dots, p-1\}$.

Let’s work through an example: $\begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} x = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}$ $= \left[\begin{array}{ccc|c} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \end{array}\right] =_{(3)-(1)} \left[\begin{array}{ccc|c} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \end{array}\right] =_{(3)-(2)} \left[\begin{array}{ccc|c} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{array}\right]$

We then solve for $x$ to get $x = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}$

In general, we will need to be familiar with the multiplicative inverse which is $b^{-1} = a \in \{1, \dots, p-1\}$ s.t. $ab = 1\ (mod\ p)$

For example, $5^{-1} = 3\ (mod\ 7)$ $4^{-1} = 2\ (mod\ 7)$ $6^{-1} = 6\ (mod\ 7)$

So, coefficients of $A$ remain in $\{0, 1, \dots, p-1\}$ and complexity $O(n^{3}\log p)$.

Can we use this to solve $Ax = b$ faster?

It turns out, YES, we can!

1. First, solve $A\bar{x}=b\ (mod\ p^m)$ for a “large enough” $m$.
2. Convert $\bar{x}$ to rational $x$ with “not too large” numerator and denominator.

We want $m$ to be large enough such that the resulting $\bar{x}$ the unique solution to $A\bar{x}=b\ (mod\ p^m)$. How large, exactly, is that?

We know that $A$ has entries with $b$ bits. So, $|det(A)| \leq (2^{2b}n)^n = 2^{(2b+\log{n})n}$

This implies that every numerator/denominator of coordinates of $x$ is an integer $q \leq 2^{(2b+\log{n})n}$.

Assume $p < 2^{2b}$ and $p$ does not divide $det(A)$.

Now, our high level approach to solving $Ax = b$ will be to take the following steps:

1. Solve $A\bar{x} = b\ (mod\ p^m)$ in $\tilde{O}(n^3 + mn^2)$.

2. Set $m = O(n\log{n})$ and recover $x$ from $\bar{x}$ such that $Ax = b$.

First, we will try to find $\frac{c_{i}}{d} = x_{i}$ where $c_i$ is a vector and $d$ is an integer with $|c_i|, d \leq q$. Why? $Ac = dA\bar{x}\ (mod\ p^m) = db\ (mod\ p^m)$ $A\frac{c}{d} = b\ (mod\ p^m)$ $|A_{i}c| \leq ||A_i|| \max_{j}|c_j| \leq 2^{2b+\log{n}}q 2^{(2b + \log{n})(n+1)}$, so $m > \frac{(2b + \log{n})(n+1)}{\log{p}}$ will suffice.

We now present the algorithm to solve the first step:

1. Find $C$ $AC = I\ (mod\ p)$

2. Set $b_0 = b$. For $i = 0 \dots m-1$ $x_i = cb_i\ (mod\ p)$ $b_{i+1} = \frac{1}{p}(b_i - Ax_i)$

3. Calculate $\bar{x}$ and $A\bar{x}$. $\bar{x} = \sum_{i=0}^{m-1} x_{i}p^{i}$
So, $A\bar{x} = \sum_{i=0}^{m-1} Ax_{i}p^{i}$ $= \sum_{i=0}^{m-1} (b_{i} - pb_{i+1})p^{i}$ $= \sum_{i=0}^{m-1} b_{i}p^{i} - b_{i+1}p^{i+1}$ $= b_0 - b_{m}p^m$ $= b_0\ (mod\ p^m)$

Next time we will look at how to approximate a given real/rational by a rational with small integers using the Euclidean algorithm for greatest common divisor. We will use this to complete the solution to $Ax=b$.