Уровень задачи

Умножение плотных матриц: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][выверенная версия]
(перенос (слияние страниц))
 
(не показаны 3 промежуточные версии 1 участника)
Строка 1: Строка 1:
== Описание свойств и структуры алгоритма ==
+
{{level-p}}
=== Общее описание алгоритма ===
+
 
=== Математическое описание ===
+
'''Перемножение матриц''' - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов.
=== Вычислительное ядро алгоритма ===
+
Здесь мы рассмотрим умножение <math>C = AB</math>&nbsp; плотных неособенных матриц, то есть тот вариант, где никак не может использоваться специальный вид матрицы<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>.
=== Макроструктура алгоритма ===
+
 
=== Описание схемы реализации последовательного алгоритма ===
+
:<math>
=== Последовательная сложность алгоритма ===
+
\begin{align}
=== Информационный граф ===
+
c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj}, \quad i \in [1, m], \quad j \in [1, l].
=== Описание ресурса параллелизма алгоритма ===
+
\end{align}
=== Описание входных и выходных данных ===
+
</math>
=== Свойства алгоритма ===
+
 
#перенаправление [[Перемножение_плотных_неособенных_матриц_(последовательный_вещественный_вариант)]]
+
Классический алгоритм - [[Перемножение_плотных_неособенных_матриц_(последовательный_вещественный_вариант)]]. Для больших размеров существуют и более быстрые алгоритмы (метод Штрассена и т.д.).
 +
 
 +
= Литература =
 +
 
 +
[[Категория:Статьи в работе]]
 +
 
 +
[[en:Dense matrix multiplication]]

Текущая версия на 14:28, 14 марта 2018


Перемножение матриц - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов. Здесь мы рассмотрим умножение [math]C = AB[/math]  плотных неособенных матриц, то есть тот вариант, где никак не может использоваться специальный вид матрицы[1].

[math] \begin{align} c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj}, \quad i \in [1, m], \quad j \in [1, l]. \end{align} [/math]

Классический алгоритм - Перемножение_плотных_неособенных_матриц_(последовательный_вещественный_вариант). Для больших размеров существуют и более быстрые алгоритмы (метод Штрассена и т.д.).

Литература

  1. В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.