A proof of the asymptotically-fastest algorithm for performing this process uses a theorem concerning the existence of integer sequences lacking three terms in arithmetic progression, as well as Schonhage's theorem.
A proof of the asymptotically-fastest algorithm for performing this process uses a theorem concerning the existence of integer sequences lacking three terms in arithmetic progression, as well as Schonhage's theorem. The first known algorithm for this process that ran in sub-classical time was numerically unstable and employed an analogue of Gauss's algorithm for complex multiplication to achieve a big-O exponent of log-base-2-of-7. Because this operation is associative, re-ordering sequences of this operation in a recursive process whose name includes the term (*) "chain" can result in improved runtimes. Strassen's algorithm and the Coppersmith-Winograd algorithm are used to perform this operation, which is performed twice to execute a change of basis. This operation corresponds to composing linear transformations. For 10 points, name this non-commutative binary operation on matrices in which the number of columns of the first matrix must equal the number of rows of the second matrix.
A proof of the asymptotically-fastest algorithm for performing this process uses a theorem concerning the existence of integer sequences lacking three terms in arithmetic progression, as well as Schonhage's theorem.
matrix multiplication [accept word forms like "multiplying matrices"; accept just multiplication after "matrix" is read]