November 2016

S M T W T F S
  1 2345
6789101112
13141516171819
20212223 242526
27282930   

Style Credit

Expand Cut Tags

No cut tags
Friday, September 12th, 2014 10:44 am
tl;dr опять про математику

А знаете ли вы, что неизвестно, какое минимальное количество умножений нужно совершить для того, чтобы умножить две матрицы 3x3? В 1976 году был придуман алгоритм с 23 умножениями. Позволю себе процитировать часть статьи:

The algorithm in this paper was produced by finding an integer solution to the following system of 729 nonlinear algebraic equations involving 621 unknowns

[...]

No use of computers was made in solving this system of equations.
Через 35 лет был придуман другой алгоритм с 23 умножениями. Алгоритма с 22 умножениями (как и доказательства того, что его не существует), насколько мне известно, нет.

Для матриц 2x2 нужно 7 умножений; есть и алгоритм, и доказательство.

Reply

From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.