![]() While it takes eight intermediate multiplications to find the product of two-by-two matrices, it takes 64 to find the product of four-by-four matrices. So to get the top-right entry, multiply the first number in the first row of A by the first number in the second column of B, then multiply the second number in the first row of A by the second number in the second column of B, and add those two products together.Īs matrices grow larger, the number of multiplications needed to find their product increases much faster than the number of additions. When computing each entry of their product, you use the corresponding row of A and corresponding column of B. To get a sense for this process, and how it can be improved, let’s start with a pair of two-by-two matrices, A and B. It’s typical of the recent painstaking gains in the field. The result, by Josh Alman, a postdoctoral researcher at Harvard University, and Virginia Vassilevska Williams of the Massachusetts Institute of Technology, shaves about one-hundred-thousandth off the exponent of the previous best mark. This is where “exponent two” comes from.Īnd while no one knows for sure whether it can be reached, researchers continue to make progress in that direction.Ī paper posted in October comes the closest yet, describing the fastest-ever method for multiplying two matrices together. More generally, the product of a pair of n-by- n matrices is another n-by- n matrix with n 2 entries.įor this reason, the fastest one could possibly hope to multiply pairs of matrices is in n 2 steps - that is, in the number of steps it takes merely to write down the answer. For example, if you start with a pair of two-by-two matrices, their product will also be a two-by-two matrix, containing four entries. When you have two matrices of compatible sizes, it’s possible to multiply them to produce a third matrix. If it’s not, then we’re stuck in a world misfit to our dreams. If exponent two is achievable, then it’s possible to carry out matrix multiplication as fast as physically possible. ![]() ![]() “Exponent two” refers to the ideal speed - in terms of number of steps required - of performing one of the most fundamental operations in math: matrix multiplication. “I want the exponent to be two because it’s beautiful.” “It’s hard to distinguish scientific thinking from wishful thinking,” said Chris Umans of the California Institute of Technology. For computer scientists and mathematicians, opinions about “exponent two” boil down to a sense of how the world should be. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |