Fast Matrix Multiplication Algorithm for a Bank of Digital Filters
Vitaly B. Kreyndelin, E. D. Grigorieva · 2021
A method of implementing matrix multiplication for use in digital filter banks (sets) is presented. This method allows to obtain noticeable savings of computational costs compared to standard methods. Reduction of computational complexity of digital filter banks (sets) is achieved without any performance loss. The method proposed in the report is based on the use of a combination of the known method of 3M multiplication of complex matrices and the Strassen method for fast multiplication of matrices. A feature of the application of the Strassen method in this case is that it is recursively applied, starting with some dimension of blocks. Multiplication of lower dimension blocks is carried out by the traditional method. In order to reduce computational complexity, the minimum dimension of blocks was selected, starting from which it is advisable to use the Strassen method. An analysis of the computational complexity of the proposed method has shown that its use in implementing a bank (set) of digital filters allows to obtain a gain in complexity compared to a traditional algorithm by about 1.8-1.9 times with large dimensions of matrices. An approximate analysis of the sensitivity of the method proposed in the article to rounding errors that occur during digital processing has been carried out. As a result of the analysis, it was found that the proposed method has approximately the same sensitivity to rounding errors as the traditional method.