Про решение СЛАУ методом Холесского.
Сооб: 1999 из 2000 -1998 RU.ALGORITHMS
От : Evgenij Masherov 2:5020/175.2 Mon 05 Jun 06 20:07
Кому: Vladimir Vassilevsky
Тема: Re: Разложение Холецкого для комплексной матрицыFrom: "Evgenij Masherov"
Mon Jun 05 2006 19:19, Vladimir Vassilevsky wrote to Evgenij Masherov:
>>>> Это один из самых лучших методов решения систем линейных уравнений
>>>> (СЛАУ), если только матрица коэффициентов симметрична.
IK>>> Hе претендуя на знание темы, хочется выяснить -- а какова
IK>>> алгоритмическая сложность? O(N), O(N^2), O( N*log(N) )?
EM>> Кубическая, увы.
EM>> Ещё не придуман практически эффективный алгоритм со сложностью, меньшей
EM>> кубической.
VV> Алгоритм Штрассена - сложность меньше кубической. Хотя оверхед, пожалуй,
VV> перевешивает выигрыш...
Hу я же подчеркнул - практически эффективный. Там, кстати, не только
коэффициент при вроде меньшем N-в-степени-log-2-от-семи великоват...
Сам не реализовывал - а один мой знакомый, для библиотеки численных методов,
заточенной под Itanium, попробовал. Из-за резкого возрастания число сложений
резко падает точность.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)