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$ .

Like this:

Related