Please note: This PhD seminar will be given online.
Stavros
Birmpilis, PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
We present a deterministic reduction to matrix multiplication for the problem of linear system solving: given as input a nonsingular $A \in \Z^{n \times n}$ and $b \in \Z^{n \times 1}$, compute $A^{-1}b$. The algorithm we give computes the minimal integer $e$ such that all denominators of the entries in $2^eA^{-1}$ are relatively prime to $2$. Then, for a $b$ that has entries with bitlength $O(n)$ times as large as the bitlength of entries in $A$, we give an algorithm to produce the $2$-adic expansion of $2^eA^{-1}b$ up to a precision high enough such that $A^{-1}b$ over $\Q$ can be recovered using rational number reconstruction. Both $e$ and the 2-adic expansion can be computed in $O(\MM(n,\log n + \log ||A||) \times (\log n) (\log n + \loglog ||A||))$ bit operations. Here, $||A||= \max_{ij} |A_{ij}|$ and $\MM(n,d)$ is the cost to multiply together, modulo $2^d$, two $n \times n$ integer matrices.
Our approach is based on the previously known reductions of linear system solving to matrix multiplication which use randomization to find an integer lifting modulus $X$ that is relatively prime to $\det A$. Here, we derandomize by first computing a permutation $P$, a unit upper triangular $M$, and a diagonal $S$ with $\det S$ a power of two, such that $U := APMS^{-1}$ is an integer matrix with $2 \perp \det U$. This allows our modulus $X$ to be chosen a power of $2$.
To join this PhD seminar on Zoom, please go to https://us02web.zoom.us/j/85446398177?pwd=TjJVU1BJN3Iwc05IS3N1bUtrVFFyZz09.
Meeting
ID:
854
4639
8177
Passcode:
199196