Jianbo Wang: Solving systems of linear equations through zero forcing set
- Speaker
- Jianbo Wang
- Affiliation
- University of Electronic Science and Technology of China
- Date
- Time
- – Asia/Shanghai
- Venue
- 518, Research Building 4
Abstract
Let $\mathbb{F}$ be any field, we consider solving $Ax=b$ for a matrix $A\in\mathbb{F}^{n\times n}$ of $m$ non-zero elements. If we are given a zero forcing set of $A$ of size $k$, we can solve the problem in $O(mk+k^\omega)$ time. The algorithm is inspired by the light chasing algorithm for grid graphs.