Спасибо! За ссылкой на github приглашаю в личку (это же не «Я пиарюсь», в самом деле!). Выслушаю все замечания к статье, починю всё, что можно, и ссылку всем отдам.

То есть первая картинка в посте не даёт ответ на этот вопрос? :)

Экономится не только и не столько процессорное время. Например, вы пишете программу, делающую нечто над конечным полем. Значит, где-то глобально должна быть выделена память как минимум под порядок этого поля. Значит, где-то её надо предварительно выделить. Вот такую неприятную необходимость можно устранить.

К тому же, не зря это помещено в Ненормальное программирование. :)

Чем он лучше %MY_FAVORITE_FRAMEWORK%?

Когда исследователи, работающие с многомерными массивами, переходят от проб и ошибок к написанию реальных быстрых расчётных программ, им, как правило, уже не нужны ленивые вычисления. Там начинаются пляски с кэшем, параллельностью и прочие оптимизации, где крайне важно знать, что, где и когда реально выполняется. Многие вообще пишут на Фортране и радуются, как он умно оптимизирует циклы. (Ну а качество кода, к сожалению, редко интересует их в эти моменты.)

Ну вот в учебнике "Матричный анализ и линейная алгебра" Е. Е. Тыртышникова, например, определитель вводится как индикатор линейной зависимости векторов, а потом уже выводится для него формула. Учебники разные бывают.
UPD. Ниже вот Morozov_5F уже упомянул эту книгу.

И в первом, и в этом варианте выглядит так, будто новый сигнал — зеркальное отражение исходного. Не знаю, на каком языке вы пишете, но вы уверены, что вам нужно fft(x, -1), а не что-то вроде ifft(x)? Дело в том, что дважды применённое прямое преобразование — это в точности разворот вектора.

И вот на горизонте замаячил fast multipole method, про который, между прочим, было бы *действительно* интересно почитать.

Ну я даже не знаю, погуглите Мариссу Мейер там, или Аду Лавлейс для начала. А минусуют вас за то, что вы сексизм разводите на ровном месте.

В свете всех найденных ошибок и неточностей у меня возникает вопрос: зачем вообще писать статью по теме, в которой разбираешься так плохо?

Нет, то, что я написал, значит другое. Чем вы читаете? Я говорю, что вы не можете найти собственные значения матрицы над конечным полем, используя существующие итерационные алгоритмы для вещественных/комплексных матриц. (На всякий случай: они не совпадают с собственными значениями этих же матриц, рассмотренных как вещественных.) Не можете ни с какой точностью, повторяю это специально для вас, хотя для меня это звучит как бессмыслица — поскольку в конечном поле нет понятия приближения.

Ну, например, потому, что у вас не будет в распоряжении понятия «точность».

Рассмотрите для простоты итерационный метод решения системы какой-нибудь. Вот вы итерируете, итерируете, и по величине невязки ||Ax_n-b|| и числу обусловленности вашей матрицы можете прикинуть, насколько вы уже близки к решению. А теперь представьте, что вы итерируете над GF(2) (поле из нуля и единицы). Вы считаете невязку, и это вектор из нулей и единиц. В нём может быть только одна единица, но вы можете быть сколь угодно далеки от решения (по Хэммингу, например). Он может быть весь из единиц, а итерационный метод — взять и сойтись на следующей итерации.

При этом, например, итерационные методы для линейных систем, основанные на подпространствах Крылова (тот же метод Ланцоша), у вас всё равно приведут к решению — поскольку это в глубине души прямые методы: за n итераций метод Ланцоша гарантированно сходится. Он считается итерационным, потому что в вещественном случае итерации можно оборвать на пол-пути, когда достигнута необходимая точность. Но для собственных чисел таких прямых алгоритмов не существует. Например, если бы вы построили такой прямой алгоритм, использующий только арифметические операции и взятие корней, вы бы пришли к нахождению корней многочленов в радикалах (потому что любому многочлену соответствует матрица, для которой он является характеристическим), что гарантированно невозможно.

Все существующие алгоритмы поиска собственных значений матриц общего вида — какими бы быстрыми и надёжными они ни были — итерационные, а это значит, что вы не можете просто взять и применить их над конечным полем. Поэтому ваше утверждение о сложности в O(n³) в конечном поле голословно и нуждается либо в ссылке, либо (что более вероятно) в широкомасштабном исследовании.

Вы QR-разложение от QR-алгоритма хорошо отличаете? Вы мне приводите ссылку на итерационный алгоритм. Как вы будете его использовать в конечных полях, где и сходимости-то как таковой не существует?

Вот это поворот! И как же QR-разложение помогает вычислять собственные значения, м?
С корнями многочленов очень даже понятно, как это делать численно — запускаете любимый алгоритм минимизации для |f(x)|² и всё. См. также Root-finding algorithms.

Да, очевидно. Ну а какой метод для нахождения собственных чисел над простыми полями вы можете посоветовать?
Потом, не ищут корни многочленов не потому, что это дорого, а потому, что это неустойчиво. Что опять-таки проблема только для поля с нулевой характеристикой.

Ну вот расскажите, как вы будете быстро над большим конечным полем корни характеристического многочлена степени выше четырёх находить.

Не квадратично. Матрица n x n сопоставляется каждому биту (или более длинной «цифре»). Размер шифротекста = размер исходного текста, умноженный на n², n — параметр.

Ну возьмите матрицу порядка 2^(n/3), будет O(2^n).
Потом, O(n^3) — это если у вас матрица вещественная или комплексная. А если над конечным полем, то не так всё просто.