(Dense Structured) Matrix Vector Multiplication

Atri Rudra (University at Buffalo, State University of New York).

Course Summary | About the lecturer | Location and schedule | Materials | Assignment

Course summary:

We will study the problem of matrix-vector multiplication. In particular, we consider the case when the matrix is dense and structured (but the vector is arbitrary). We will study the arithmetic complexity of this operation with the goal of identifying when we can perform this operation in near-linear number of operations. This is a very fundamental problem that has many (practical) applications. While it is not possible to cover these applications, we will use two case studies to motivate our study: (1) error-correcting codes and (2) (single layer) neural networks.

Along the way, we will study some nice results that hold for matrix-vector multiplication but are perhaps not as well-known as they should be (or at least were not known to me a few years back!): as a bonus these results will illustrate why arithmetic complexity is a nice lens to study matrix-vector multiplication under.

The technical results will hinge on some close connections of a large class of structured matrices with polynomials (both structured and not) as well as fast algorithms for basic polynomials operations. This course will assume knowledge of basic linear algebra (matrices, vectors, notions of linear independence and rank of matrices and so on) and familiarity with fields. Familiarity with algorithms for basic operations on polynomials is a bonus but is not required.

About the lecturer:

Atri Rudra is an Associate Professor of Computer Science and Engineering at University at Buffalo, State University of New York. Atri received his Bachelor's degree from the Indian Institute of Technology, Kharagpur, India in 2000 and his Ph.D. from University of Washington in 2007. From 2000 to 2002, he was a Research Staff Member at IBM India Research Lab, New Delhi, India. His research interests lie in theoretical computer science and in particular, theory of error-correcting codes, database algorithms, linear algebra algorithms, sub-linear algorithms, computational complexity, finite field theory and applications. He is a recipient of an NSF CAREER award (2009), HP Labs Innovation Research Award (2010), ESA best paper award (2010), UB Exceptional Scholars - Young Investigator award (2011), PODS best paper awards (2012 and 2016), IBM Faculty Award (2013), UB SEAS Senior Teacher of the Year Award (2015) and SIGMOD Research Highlights (2016).

Location and schedule:

MIMUW building, room 5440.

Thursday, May 24
14:15 - 15:45 lecture
15:45 - 16:00coffee and cake
16:00 - 17:00 class
Friday, May 25
14:15 - 15:45 lecture
15:45 - 16:00 coffee and cake
16:00 - 17:00 class
Saturday, May 26
10:15 - 11:30 lecture
11:30 - 11:45 coffee and cake
11:45 - 13:00 class

Lecture notes - tentative version

Assignment:problem set. Please submit the solutions through moodle (registration key PHDOPEN1718.2358) by Sunday June 17.