Jianbo Wang: Solving systems of linear equations through zero forcing set

Speaker:

Jianbo Wang (University of Electronic Science and Technology of China)

Time:

  • 16:20-17:20 (Time in Beijing)
  • November 18, 2022 (Friday)

Venue:

518, Research Building 4

Abstract:

Let F\mathbb{F} be any field, we consider solving Ax=bAx=b for a matrix AFn×nA\in\mathbb{F}^{n\times n} of mm non-zero elements. If we are given a zero forcing set of AA of size kk, we can solve the problem in O(mk+kω)O(mk+k^\omega) time. The algorithm is inspired by the light chasing algorithm for grid graphs.

,