PhD Seminar • Symbolic Computation | Computer Algebra — Deterministic Reduction of Integer Nonsingular Linear System Solving to Matrix MultiplicationExport this event to calendar

Friday, August 21, 2020 1:00 PM EDT

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

Location 
Online PhD seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2024 (100)
    1. April (23)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)