Booth Id:
MATH002
Category:
Mathematics
Year:
2022
Finalist Names:
Zhang, Meryl (School: R. C. Clark High School)
Abstract:
Matrix multiplication is the fundamental building block of machine learning. All neural networks, when being trained, use matrix multiplication. However, multiplying a significantly large number of matrices is painfully slow. There is already an existing algorithm that is faster than the standard matrix multiplication algorithm, known as Strassen's Algorithm, where the matrix is split into four different parts, multiplied, then pieced back together. However, for smaller matrices, the standard matrix multiplication algorithm would actually be faster due to the asymptotic complexity of Strassen’s. Therefore, the purpose of this experiment is to find the crossover point, of which the standard matrix multiplication algorithm is faster than Strassen’s algorithm. In order to find the crossover point, different crossover points of 1 to 256 were tested on matrices of size 1009, 1020, and 1024. It was observed that the runtime stopped significantly decreasing when the crossover was around 126. When Strassen’s Algorithm with a crossover of 126 was run, it outperformed the standard matrix multiplication algorithm by approximately 0.1 seconds. The increased efficiency of this hybrid matrix multiplication algorithm would significantly improve the rates of which scientific advancements are introduced, such innovations would include AI models used to detect cancer, security software to catch fraud, facial recognition on one’s phone, and any technological invention that would use neural networks and matrix multiplication!
Awards Won:
National Security Agency Research Directorate : Third Place Award “Mathematics”