In this paper, we present novel deterministic algorithms for multiplying two n n matrices approximately. Given two matrices A B we return a matrix C which is an emph{approximation} to C = A B . We consider the notion of approximate matrix multiplication in which the objective is to make the Frobenius norm of the error matrix C ? C arbitrarily small. Our main contribution is to first reduce the matrix multiplication problem to solving a set of linear equations and then use standard techniques to find an approximate solution to that system in O ( n 2 ) time. To the best of our knowledge this the first examination into designing quadratic time deterministic algorithms for approximate matrix multiplication which guarantee arbitrarily low emph{absolute error} w.r.t. Frobenius norm.
展开▼
