首页    期刊浏览 2025年02月22日 星期六
登录注册

文章基本信息

  • 标题:Fast Approximate Matrix Multiplication by Solving Linear Systems
  • 本地全文:下载
  • 作者:Shiva Manne ; Manjish Pal
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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.

  • 关键词:Approximate Matrix Multiplication ; Deterministic Algorithm ; error vector ; frobenius norm ; iterative method ; matrix multiplication ; Positive Definite Linear Systems ; vector norm
国家哲学社会科学文献中心版权所有