[программирование] Интересная задача

Разве обратные матрицы не за O(N^2) считаются? *сошкребывает с черепа воспоминания о Гауссе*

Хорошо подумал, устыдился и осознал, что метод Гаусса работает за O(N^3). Не так уж и медленно, имхо.

>Разве обратные матрицы не за O(N^2) считаются?

Википедия говорит, что за O(N^3)

DLANGE, DGETRF, DGECON, DGETRI

>Не так уж и медленно, имхо.

Признаюсь честно - не знаю, брать большие матрицы не пробовал. Но мне всегда казалось, что находить обратные матрицы размером 10 000 x 10 000 (и более) не вариант, по причине очень большого времени расчета.

Обратная матрица нужна далеко не всегда. В частности, для решения СЛАУ и ЛМУ обычно вполне достаточно LU-, QR- или SVD-разложения.

> Но мне всегда казалось, что находить обратные матрицы размером 10 000 x 10 000 (и более) не вариант, по причине очень большого времени расчета.

man число обусловленности матрицы. Оно при больших размерностях начинает сильно срать в погрешность.

Что интересного в перекладывании матриц, и вообще, байтиков, на стеке? Это говно какое-то, для 16-летних дебилов.

10 000 x 10 000

это фигня. вот 1000 000 x 1000 000,
в реальном времени - это достойная задача

>Что интересного в перекладывании матриц, и вообще, байтиков, на стеке? Это говно какое-то, для 16-летних дебилов.

В самом перекладывании матриц, ради перекладывания нет ничего интересного. Но если бы появилась возможность считать обратные матрицы большого размера, то как я понимаю это могло бы дать большой прогресс в некоторых физических расчетах.

Если хочешь, можно другу задачу. Есть конденсатор, состоящий из двух пластин. Эти пластины расположены не параллельно, а как-то произвольно друг к другу. Подаем напряжение на пластины, надо определить характер распределения зарядов. У меня были мысли решить эту задачу через обратные матрицы. Но с большими размерами матриц в итоге выходит жопа. А так было бы красиво. Есть характеристика (что то типа электроемкости), которая зависит от геометрии, и не зависит от электрических величин.

Это говно какое-то

предложи свои, интересные задачи, с домино и шпалоукладчицами

заполненная или разреженная?

итерационные методы спасают

> Есть характеристика (что то типа электроемкости), которая зависит от геометрии, и не зависит от электрических величин.

Угу, взаимная емкость(да и просто емкость) — это чисто геометрическая характеристика.

Итерационные методы лишь сдвигают коэффициент в погрешности. Принципиально этот вопрос не решают.

да у хотя бы вот:
портировать этот вот генератор парсеров на свой любимый язык.
http://love5an.livejournal.com/tag/peg

>итерационные методы спасают

От плохо обусловленных матриц спасает только вдоль.

>портировать этот вот генератор парсеров на свой любимый язык.

Не флейма ради, интереса для (раз ты собаку съел на парсинге):

1. peg vs. any other parser

2. peg vs. автоматы

3. парсеры, расширяемые _при парсинге_ (а-ля лисповый ридер)

Интересует только твоё ИМХО, не хочешь писать - не пиши, к документации отправлять не надо, хотя если есть на примете интересные статьи по вопросам - приму с благодарностью :)

Сдается мне, автор толстый тролль... Что интересного в задаче, мат. методы решения которой обсосаны минимум стопицот раз? Для симметричных, несимметричных, разреженных, трехдиагональных, и прочая и прочая...

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

>Сдается мне, автор толстый тролль...

Спасибо. :)

...мат. методы решения которой обсосаны минимум стопицот раз? Для симметричных...

Ты знаешь очень быстрый алгоритм нахождения обратной матрицы, для случая симметричной матрицы? Links or GTFO^W^W^WДай ссылки.

Я в одно время долго искал быстрый алгоритм в гугле. Но потом понял, что гугл мне не друг. Скорее всего быстрого алгоритма не существует. Я решил задать этот вопрос просто так. А вдруг кто-то даст нужный мне ответ?

У Кнута во второй главе раздел 2.2.6 алгоритм S реализует осевое преобразование разреженной матрицы. Там же ссылки на другие работы, а в упражнениях есть тестовые примеры.

портировать этот вот генератор парсеров на свой любимый язык

и что в этом интересного?

Видимо, автор не торопится отвечать :)