|
Записки научных семинаров ЛОМИ, 1982, том 118, страницы 159–187
(Mi znsl3979)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Верхние оценки сложности решения систем линейных уравнений
В. И. Солодовников
Аннотация:
Статья носит обзорный характер и посвящена прямым (точным) методам решения систем линейных уравнений, которые рассматриваются с точки зрения их вычислительной сложности. Для большинства алгоритмов приводятся в общих чертах идеи их построения. Статья состоит из двух частей. В первой части рассматриваются методы последовательного решения систем линейных уравнений. Сюда вошли алгоритмы Гаусса Коновальцева, алгоритм Штрассена и его модификации, результаты Юна и Густавсона для теплицевых систем и др. Вторая часть посвящена параллельному решению систем линейных уравнений. Здесь рассматриваются распараллеливание алгоритма Гаусса, результаты Яфиля и Кунга по оценке сложности параллельного решения треугольных систем, результаты Ксанки, основанные на распараллеливании метода Леверье, общий результат Яфиля о распараллеливании неветвящихся программ вычисления многочленов, алгоритм Стоуна для параллельного решения трехдиагоналышх систем. Приводятся несколько новых оценок. В частности, если умножение пары $(n\times n)$-матриц возможно последовательно при помощи не ветвящейся программы со сложностью $O(n^\alpha)$, то решение произвольной системы $m$ линейных уравнений с $n$ неизвестными на $p$ процессорах возможно со сложностью
$$
O\left(\frac{\max(m, n)\min(m, n)^{\alpha-1}}{p}+\min(m, n)\log_2\max(m, n)\right),
$$
а решение треугольной системы размера $n$ возможно со сложностью
$$
O\left(\frac{n^2}{p}+\frac{n}{p^{1/\alpha}}\log_2^{1-\frac{1}{\alpha}}n+\log_2^2n\right).
$$
Образец цитирования:
В. И. Солодовников, “Верхние оценки сложности решения систем линейных уравнений”, Теория сложности вычислений. I, Зап. научн. сем. ЛОМИ, 118, Изд-во «Наука», Ленинград. отд., Л., 1982, 159–187
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl3979 https://www.mathnet.ru/rus/znsl/v118/p159
|
Статистика просмотров: |
Страница аннотации: | 600 |
|