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.

Advertisements