Virginia Williams from Stanford University proposed an algorithm for multiplying square matrices with the best asymptotic complexity to date ( pdf ). The previous record holder, the Coppersmith-Winograd algorithm, was proposed in 1987, and its complexity estimate was nicknamed the barrier of the same name.

Traditionally, asymptotic estimates are used for complexity analysis. In fact, they talk about the speed at which the number of computational operations grows with increasing algorithm parameters (in this case, there is only one parameter - the size of the square matrix n). The multiplication algorithm “by definition,” that is, by rows and columns, has a complexity of O(n3), that is, its complexity grows approximately as a constant multiplied by a power function with exponent 3.

In the 1980s, Don Coppersmith and Shnuel Winograd proposed an algorithm for calculating matrix multiplication with complexity O(n2.39). They then noticed that splitting the matrix before multiplying it into submatrices and applying the algorithm to them allowed the complexity to reach a record O(n2,376). This result was obtained by dividing n into two. Further divisions, however (into three, four, and so on) did not bring improvement.

Williams' new work improved upon Coppersmith and Winograd's original assessment. As a result, she was able to show that when n is divided into 8 parts, the asymptotic complexity turns out to be equal to O(n2.3727). Despite the fact that the improvement was obtained only in the third digit, according to experts, the work is of interest, since the Coppersmith-Winograd barrier lasted 24 years. Many scientists believe that there is an algorithm with an asymptotic estimate of O(n2), that is, the complexity grows as the number of elements in a square matrix.

The work emphasizes that this algorithm will not find application in existing computing systems for the same reason that the Coppersmith-Winograd algorithm is not used - reducing complexity leads to an increase in the memory required for operation. At the same time, the memory of modern computers is not enough to apply such algorithms in real problems. Instead, Strassen's algorithm is often used .

Mathematicians have overcome the Coppersmith-Winograd barrier