Randomization of approximate bilinear computation for matrix multiplication. Issue 1 (2nd January 2021)

• Record Type: Journal Article
• Authors: Malik, Osman Asif; Becker, Stephen
• Is Part Of: International journal of computer mathematics. Volume 6:Issue 1(2021)
• Page Start: 54
• Page End: 93
• Publication Date: 2021-01-02
• Subjects: Randomized algorithms -- approximate algorithms -- matrix multiplication -- Strassen's algorithm; 15-02 -- 65F30; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2020.1861104
• Languages: English
• ISSNs: 2379-9927

Abstract

ABSTRACT: We present a method for randomizing formulas for bilinear computation of matrix products which does not increase the leading order complexity of the computation. We consider the implications of such randomization when there are two sources of error. The first source is due to the computation formula itself only being approximately correct. Such formulas come up when numerically searching for faster matrix multiplication algorithms. The second source is due to using floating point arithmetic. This kind of error is especially important when computing on low precision hardware like GPUs. Our theoretical results and numerical experiments indicate that our method can improve performance when the two kinds of error are present individually, as well as when they are present at the same time.