|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stanislav Shwartsman 2:400/520 05 Jun 2001 20:05:58
To : Evgenij Masherov
Subject : Вычисление определителя
--------------------------------------------------------------------------------
05 Jun 01 13:12, you wrote to Abbat:
A>> Требуется алгоритм вычисления определителя (>15 порядка) за
A>> приемлемое время.
EM> Если умеете решать матрицу (в смысле систему линейных уравнений,
EM> коэффициенты левой части которых содержатся в заданной матрице)
EM> Жорданом-Гауссом (или одним Гауссом) - то перемножаете ведущие
EM> элементы. Это и будет определитель. Сложность O(n^3).
Есть более быстрый алгоритм, основанный на методе LU-Decomposition.
У меня это еще свежо в памяти, так как я только что можно сказать закончил
задание-соревнование на программу, считающую детерминант (типа у кого
быстрее будет). Выиграл между прочим.
Самый оптимальный алгоритм на данный момент - LU Decomposition. Время
работы не более (1/3)*(n^3). Его версия с сайта algolist.da.ru примерно
в 5 раз утсупает по скорости моей финальной. Моя же основана на реализации
алгоритма фирмы Intel и исходнике взятом с их сайта. Между прочим там же
есть и версия, которая использует SSE-инструкции и за счет этого делает
всех по скорости работы просто в разы (всех, включая мою финальную версию,
не использующую технику SSE).
Если есть желание - могу выслать и алгоритм и реализации (все, какие есть).
E-mail: gate@fidonet.org.il
Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
Bye !
Stanislav (AKA Night's Man) [Team Technion]
---
* Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Вычисление определителя 