Библиотека алгоритмов: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
 
(не показаны 32 промежуточные версии этого же участника)
Строка 1: Строка 1:
 
=='''УМНОЖЕНИЕ МАТРИЦЫ НА ВЕКТОР'''==
 
=='''УМНОЖЕНИЕ МАТРИЦЫ НА ВЕКТОР'''==
 +
[[Файл:XYprojection1.jpg|мини|XY projection]]
 
=====Ссылка на описание в энциклопедии AlgoWiki:=====
 
=====Ссылка на описание в энциклопедии AlgoWiki:=====
 
[https://algowiki-project.org/ru/Умножение_плотной_неособенной_матрицы_на_вектор_(последовательный_вещественный_вариант) Умножение плотной неособенной матрицы на вектор]</br>
 
[https://algowiki-project.org/ru/Умножение_плотной_неособенной_матрицы_на_вектор_(последовательный_вещественный_вариант) Умножение плотной неособенной матрицы на вектор]</br>
  
−
[[Файл:Умножение_матрицы_на_вектор.jpg|мини|XY projection]]
 
−
[[Файл:Умножение_матрицы_на_вектор.jpg|мини|YZ projection]]
 
−
[[Файл:Умножение_матрицы_на_вектор.jpg|мини|XZ projection]]
 
 
=====Реализация алгоритма на Си:=====
 
=====Реализация алгоритма на Си:=====
−
for(int i = 0; i < size; i++)
+
for(int i = 0; i < size; i++)</br>
−
:  for(int j = 0; j < size ; j++)
+
:  for(int j = 0; j < size ; j++)</br>
−
::      vec_out[i] += matrix[i][j] * vec _in[j];  
+
::      vec_out[i] += matrix[i][j] * vec _in[j]; </br>
 +
 
 
=====Описание алгоритма на Algolang:=====
 
=====Описание алгоритма на Algolang:=====
 
<algo></br>
 
<algo></br>
 
:    <params></br>
 
:    <params></br>
−
::      <param name="size" type="int" value="5"></param></br>
+
::      <param name="n" type="int" value="5"></param></br>
−
:    </params><br>
+
::      <param name="m" type="int" value="4"></param></br>
 +
:    </params></br></br>
 
:    <block dims="2"></br>
 
:    <block dims="2"></br>
−
::      <arg name="i" val="0..size-1"></arg></br>
+
::      <arg name="i" val="1..m"></arg></br>
−
::      <arg name="j" val="1..size"></arg></br>
+
::      <arg name="j" val="1..n+1"></arg></br>
−
::      <vertex condition="" type="2"></br>
+
::      <vertex condition="j>1" type="2"></br>
 
:::          <in src="i,j-1"></in></br>
 
:::          <in src="i,j-1"></in></br>
 
::      </vertex></br>
 
::      </vertex></br>
 
:    </block></br>
 
:    </block></br>
 
</algo></br>
 
</algo></br>
 +
=====Характеристики алгоритма (Для умножения матрицы размером m строк на n столбцов на вектор порядка n):=====
 +
* Общее количество вершин: m*n+m
 +
* Длина критического пути: n
 +
* Каноническая ширина ЯПФ: m
 +
На рисунках представлен  результат для матрицы размером 4*5 и вектора длины 5</br>
  
 
=='''ПЕРЕМНОЖЕНИЕ МАТРИЦ'''==
 
=='''ПЕРЕМНОЖЕНИЕ МАТРИЦ'''==
 +
[[Файл:XYprojection2.jpg|мини|XY projection]]
 +
[[Файл:YZprojection_2.jpg|мини|YZ projection]]
 +
[[Файл:XZprojection2.jpg|мини|XZ projection]]
 +
=====Ссылка на описание в энциклопедии AlgoWiki:=====
 +
[https://algowiki-project.org/ru/Перемножение_плотных_неособенных_матриц_(последовательный_вещественный_вариант) Перемножение плотных неособенных матриц]</br>
 +
 +
=====Реализация алгоритма на Си:=====
 +
for ( int i=0; i<size_1_str;i++)</br>
 +
:  for (int j=0; j<size_2_col;j++)</br>
 +
:  {</br>
 +
::      matrix_out[i][j]=0; </br>
 +
::      for(int k=0; k<size_common;k++) </br>
 +
:::        matrix_out[i][j]+=matrix_1[i][k]*matrix_2[k][j]; </br>
 +
:  }</br>
 +
 +
=====Описание алгоритма на Algolang:=====
 +
<algo></br>
 +
:    <params></br>
 +
::      <param name="m" type="int" value="4"></param></br>
 +
::      <param name="n" type="int" value="5"></param></br>
 +
::      <param name="l" type="int" value="6"></param></br>
 +
:    </params></br></br>
 +
 +
:    <block id="1" dims="3"></br>
 +
::      <arg name="i" val="1..m"></arg></br>
 +
::      <arg name="j" val="1..l"></arg></br>
 +
::      <arg name="k" val="1..n+1"></arg></br>
 +
::      <vertex condition="k>1" type="3"></br>
 +
:::          <in src="i,j,k-1"></in></br>
 +
::      </vertex></br>
 +
:    </block></br>
 +
</algo></br>
 +
=====Характеристики алгоритма (Для умножения матрицы размером m строк на n столбцов на матрицу размером n строк на l столбцов):=====
 +
* Общее количество вершин: m*n*l
 +
* Длина критического пути: n
 +
* Каноническая ширина ЯПФ: m*l
 +
На рисунках представлено изображение графа алгоритма выходных данных для случая перемножения двух квадратных матриц порядка 4*5 и 5*6</br></br></br></br></br></br></br></br></br></br></br></br>
 +
 +
=='''НАХОЖДЕНИЕ СУММЫ ЭЛЕМЕНТОВ МАССИВА СДВАИВАНИЕМ'''==
 +
[[Файл:XYprojection3.jpg|мини|XY projection]]
 +
=====Ссылка на описание в энциклопедии AlgoWiki:=====
 +
[https://algowiki-project.org/ru/Нахождение_суммы_элементов_массива_сдваиванием Нахождение суммы элементов массива сдваиванием]</br>
 +
 +
=====Реализация алгоритма на Си:=====
 +
for(int i=1;i<=h;i++)</br>
 +
:  for(int j=0;j<arr_size;j++)</br>
 +
::      if(j<(arr_size/(pow(2,i))))</br>
 +
:::        arr[j]=arr[j*2]+arr[2*j+1]; </br>
 +
 +
=====Описание алгоритма на Algolang:=====
 +
<algo></br>
 +
:    <params></br>
 +
::      <param name="n" type="int" value="8"></param></br>
 +
:    </params></br></br>
 +
 +
:    <block dims="2"></br>
 +
::      <arg name="i" val="1..((2)log(n)+1)"></arg></br>
 +
::      <arg name="j" val="1..n"></arg></br>
 +
::      <vertex condition="(i>1)and(j<=(n/(2^(i-1))))" type="1"></br>
 +
:::          <in src="i-1,j*2-1"></in></br>
 +
:::          <in src="i-1,j*2"></in></br>
 +
::      </vertex></br>
 +
:    </block></br>
 +
</algo></br>
 +
=====Характеристики алгоритма (для суммирования массива порядка n):=====
 +
* Общее количество вершин: n-1
 +
* Длина критического пути: [Log<sub>2</sub>n]
 +
* Каноническая ширина ЯПФ: n
 +
На рисунке изображён граф алгоритма. В данном случае выполнено суммирование 8 элементов массива. Вершины, соответствующие входным данным, обозначены октаэдром.</br>
 +
 +
=='''ПОСЛЕДОВАТЕЛЬНО-ПАРАЛЛЕЛЬНЫЙ МЕТОД СУММИРОВАНИЯ'''==
 +
[[Файл:XYprojection5.jpg|мини|XY projection]]
 +
=====Ссылка на описание в энциклопедии AlgoWiki:=====
 +
[https://algowiki-project.org/ru/Последовательно-параллельный_метод_суммирования Последовательно-параллельный метод суммирования]</br>
 +
 +
=====Описание алгоритма на Algolang:=====
 +
<algo></br>
 +
:    <params></br>
 +
::      <param name="n" type="int" value="25"></param></br>
 +
::      <param name="p" type="int" value="5"></param></br>
 +
:    </params></br></br>
 +
 +
:    <block id="0" dims="2"></br>
 +
::      количество процессоров
 +
::      <arg name="i" val="1..p"></arg></br>
 +
::      на каждый процессор, кроме одного, распределяется одинаковое количество
 +
::      элементов массива (n/p, округленное в бОльшую сторону)
 +
::      <arg name="j" val="1..n"></arg></br>
 +
::      <arg name="j" val="1..ceil(n/p)"></arg></br></br>
 +
 +
::      сумма элементов массива, равномерно распределенных по (p-1) процессорам
 +
::      <vertex condition="(j>1)and(i>1)and(j<ceil(n/p))" type="1"></br>
 +
:::          <in src="i,j-1"></in></br>
 +
::      </vertex></br></br>
 +
 +
::      сумма оставшихся эелементов
 +
::      <vertex condition="(j>1)and(i=1)and(j<=(n-p-(ceil(n/p)-1)*(p-1)))" type="1"></br>
 +
:::          <in src="i,j-1"></in></br>
 +
::      </vertex></br></br>
 +
 +
::      последовательное суммирование получившихся сумм на одном из процессоров
 +
::      <vertex condition="(i>2)and(j=ceil(n/p))" type="1"></br>
 +
:::          <in src="i-1,j"></in>
 +
:::          <in  src="i,j-1"></in>
 +
::      </vertex></br>
 +
::      <vertex condition="(i=2)and(j=ceil(n/p))" type="1"></br>
 +
:::          <in src="i-1,n-p-(ceil(n/p)-1)*(p-1)"></in></in>
 +
:::          <in src="i,j-1"></in>
 +
::      </vertex></br>
 +
:    </block></br>
 +
</algo></br>
 +
=====Характеристики алгоритма (Для суммирования массива порядка n):=====
 +
* Общее количество вершин: n-1
 +
* Длина критического пути:
 +
**ceil(n/p)-1 - суммирования по частям массива (p ветвей)
 +
**p-1 - одна последовательная ветвь
 +
* Каноническая ширина ЯПФ: p
 +
На рисунке изображён граф алгоритма без входных и выходных данных для случая суммирования 25 элементов массива на 5 процессорах.</br>
 +
=='''Компактная схема метода Гаусса для трёхдиагональной матрицы'''==
 +
[[Файл:XYprojection4.jpg|мини|XY projection]]
 +
=====Ссылка на описание в энциклопедии AlgoWiki:=====
 +
[https://algowiki-project.org/ru/Компактная_схема_метода_Гаусса_для_трёхдиагональной_матрицы,_последовательный_вариант Компактная схема метода Гаусса для трёхдиагональной матрицы]</br>
 +
 +
=====Описание алгоритма на Algolang:=====
 +
<algo></br>
 +
:    <params></br>
 +
::      <param name="n" type="int" value="6"></param></br>
 +
:    </params></br></br>
 +
 +
:    <block id="0" dims="2"></br>
 +
::      <arg name="j" val="1..n"></arg>
 +
::      <arg name="i" val="1..n"></arg></br></br>
 +
 +
::      деление
 +
::      <vertex condition="(i=j+1)and(j>1)" type="1"></br>
 +
:::          <in src="j,j"></in></br>
 +
::      </vertex></br></br>
 +
 +
::      вычетание
 +
::      <vertex condition="(j=i)and(j>1)" type="2"></br>
 +
:::          <in src="j,i-1"></in></br>
 +
::      </vertex></br></br>
 +
 +
::      умножение
 +
::      <vertex condition="j=i+1" type="3"></br>
 +
:::          <in src="j-1,i+1"></in></br>
 +
::      </vertex></br>
 +
:    </block></br>
 +
</algo></br>
 +
=====Характеристики алгоритма (Для матрицы с рангом n):=====
 +
* Общее количество вершин: 3n-3
 +
* Длина критического пути:
 +
**n−1 ярусов делений
 +
**n−1 ярусов умножений
 +
**n−1 ярусов сложений (вычитаний)
 +
* Каноническая ширина ЯПФ: 1
 +
На рисунке изображён граф алгоритма для n=6.</br>
 +
 +
=='''Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки'''==
 +
[[Файл:XYprojection6.jpg|мини|XY projection]]
 +
=====Ссылка на описание в энциклопедии AlgoWiki:=====
 +
[https://algowiki-project.org/ru/Простой_алгоритм_Кули-Тьюки_быстрого_преобразования_Фурье_для_степеней_двойки Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки]</br>
 +
 +
=====Описание алгоритма на Algolang:=====
 +
<algo></br>
 +
:    <params></br>
 +
::      <param name = "N" type = "int" value = "3"></param></br>
 +
:    </params></br></br>
 +
 +
:    <block id="0" dims="2"></br>
 +
::      <arg name = "I" val = "1..N"></arg></br>
 +
::      <arg name = "J" val = "1..2^N"></arg></br></br>
 +
 +
::      <vertex condition = "(J - 1) % (2^I) < 2^(I - 1)" type = "1"></br>
 +
:::          <in src = "I - 1, J"></in></br>
 +
:::          <in src = "I - 1, J + 2^(I -1)"></in></br>
 +
::      </vertex></br></br>
 +
 +
::      <vertex condition = "(J - 1) % (2^I) >= 2^(I - 1)" type = "2"></br>
 +
:::          <in src = "I - 1, J"></in></br>
 +
:::          <in src = "I - 1, J - 2^(I - 1)"></in></br>
 +
::      </vertex></br></br>
 +
 +
:    </block></br>
 +
</algo></br>
 +
=====Характеристики алгоритма (Для вектора с размерностью n):=====
 +
* Общее количество вершин: n*log<sub>2</sub>n
 +
* Длина критического пути:
 +
**log<sub>2</sub>n операций комплексного сложения/вычитания
 +
** log<sub>2</sub>n операций комплексного умножения
 +
* Каноническая ширина ЯПФ: n
 +
На рисунке изображён граф алгоритма для n=8.</br>
 +
 +
=='''Метод Гивенса (вращений) QR-разложения квадратной матрицы'''==
 +
[[Файл:XYprojection7.jpg|мини|XY projection]]
 +
[[Файл:YZprojection7.jpg|мини|YZ projection]]
 +
[[Файл:XZprojection7.jpg|мини|XZ projection]]
 +
=====Ссылка на описание в энциклопедии AlgoWiki:=====
 +
[https://algowiki-project.org/ru/Метод_Гивенса_(вращений)_QR-разложения_квадратной_матрицы_(вещественный_точечный_вариант) Простой алгоритм Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный точечный вариант)]</br>
 +
 +
=====Описание алгоритма на Algolang:=====
 +
<algo>
 +
: <params>
 +
:: <param name="n" type="int" value="5"></param>
 +
: </params>
 +
 +
: <block dims="3">
 +
:: <arg name="k" val="1..n-1"></arg>
 +
:: <arg name="i" val="1..n-1"></arg>
 +
:: <arg name="j" val="1..n"></arg>
 +
 +
:: выполнение поворота 2-мерного вектора 1 яруса
 +
:: <vertex condition="(j>k)and(i=k)and(k=1)" type="2">
 +
::: <in src="k,i,k"></in>
 +
:: </vertex>
 +
 +
:: выполнение поворота 2-мерного вектора 1 яруса
 +
:: <vertex condition="(j>k)and(i>k)and(k=1)" type="2">
 +
::: <in src="k,i,k"></in>
 +
::: <in src="k,i-1,j"></in>
 +
:: </vertex>
 +
 +
:: выполнение поворота 2-мерного вектора остальных ярусов
 +
:: <vertex condition="(j>k)and(k>1)and(i=k)" type="2">
 +
::: <in src="k,i,k"></in>
 +
::: <in src="k-1,i,j"></in>
 +
::: <in src="k-1,i-1,j"></in>
 +
:: </vertex>
 +
 +
:: операция вычисления параметров поворота остальных ярусов
 +
:: <vertex condition="(j=k)and(k>1)and(i=k)" type="1">
 +
::: <in src="k-1,i,j"></in>
 +
::: <in src="k-1,i-1,j"></in>
 +
:: </vertex>
 +
 +
:: выполнение поворота 2-мерного вектора остальных ярусов
 +
:: <vertex condition="(j>k)and(k>1)and(i>k)" type="2">
 +
::: <in src="k,i,k"></in>
 +
::: <in src="k-1,i,j"></in>
 +
::: <in src="k,i-1,j"></in>
 +
:: </vertex>
 +
 +
:: операция вычисления параметров поворота остальных ярусов
 +
:: <vertex condition="(j=k)and(k>1)and(i>k)" type="1">
 +
::: <in src="k-1,i,j"></in>
 +
:: </vertex>
 +
: </block>
 +
</algo>
 +
=====Характеристики алгоритма (Для матрицы порядка n):=====
 +
* Общее количество вершин: n<sup>3</sup>/3
 +
* Длина критического пути:
 +
**2n−3 макровершины вычисления параметров поворота
 +
**n−1  макровершин поворотов
 +
* Каноническая ширина ЯПФ: n
 +
На рисунке изображён Граф алгоритма без отображения входных и выходных данных для n=5.</br>

Текущая версия на 21:37, 17 мая 2021

Содержание

1 УМНОЖЕНИЕ МАТРИЦЫ НА ВЕКТОР

XY projection
1.1 Ссылка на описание в энциклопедии AlgoWiki:

Умножение плотной неособенной матрицы на вектор

1.2 Реализация алгоритма на Си:

for(int i = 0; i < size; i++)

for(int j = 0; j < size ; j++)
vec_out[i] += matrix[i][j] * vec _in[j];
1.3 Описание алгоритма на Algolang:

<algo>

<params>
<param name="n" type="int" value="5"></param>
<param name="m" type="int" value="4"></param>
</params>

<block dims="2">
<arg name="i" val="1..m"></arg>
<arg name="j" val="1..n+1"></arg>
<vertex condition="j>1" type="2">
<in src="i,j-1"></in>
</vertex>
</block>

</algo>

1.4 Характеристики алгоритма (Для умножения матрицы размером m строк на n столбцов на вектор порядка n):
  • Общее количество вершин: m*n+m
  • Длина критического пути: n
  • Каноническая ширина ЯПФ: m

На рисунках представлен результат для матрицы размером 4*5 и вектора длины 5

2 ПЕРЕМНОЖЕНИЕ МАТРИЦ

XY projection
YZ projection
XZ projection
2.1 Ссылка на описание в энциклопедии AlgoWiki:

Перемножение плотных неособенных матриц

2.2 Реализация алгоритма на Си:

for ( int i=0; i<size_1_str;i++)

for (int j=0; j<size_2_col;j++)
{
matrix_out[i][j]=0;
for(int k=0; k<size_common;k++)
matrix_out[i][j]+=matrix_1[i][k]*matrix_2[k][j];
}
2.3 Описание алгоритма на Algolang:

<algo>

<params>
<param name="m" type="int" value="4"></param>
<param name="n" type="int" value="5"></param>
<param name="l" type="int" value="6"></param>
</params>

<block id="1" dims="3">
<arg name="i" val="1..m"></arg>
<arg name="j" val="1..l"></arg>
<arg name="k" val="1..n+1"></arg>
<vertex condition="k>1" type="3">
<in src="i,j,k-1"></in>
</vertex>
</block>

</algo>

2.4 Характеристики алгоритма (Для умножения матрицы размером m строк на n столбцов на матрицу размером n строк на l столбцов):
  • Общее количество вершин: m*n*l
  • Длина критического пути: n
  • Каноническая ширина ЯПФ: m*l

На рисунках представлено изображение графа алгоритма выходных данных для случая перемножения двух квадратных матриц порядка 4*5 и 5*6











3 НАХОЖДЕНИЕ СУММЫ ЭЛЕМЕНТОВ МАССИВА СДВАИВАНИЕМ

XY projection
3.1 Ссылка на описание в энциклопедии AlgoWiki:

Нахождение суммы элементов массива сдваиванием

3.2 Реализация алгоритма на Си:

for(int i=1;i<=h;i++)

for(int j=0;j<arr_size;j++)
if(j<(arr_size/(pow(2,i))))
arr[j]=arr[j*2]+arr[2*j+1];
3.3 Описание алгоритма на Algolang:

<algo>

<params>
<param name="n" type="int" value="8"></param>
</params>

<block dims="2">
<arg name="i" val="1..((2)log(n)+1)"></arg>
<arg name="j" val="1..n"></arg>
<vertex condition="(i>1)and(j<=(n/(2^(i-1))))" type="1">
<in src="i-1,j*2-1"></in>
<in src="i-1,j*2"></in>
</vertex>
</block>

</algo>

3.4 Характеристики алгоритма (для суммирования массива порядка n):
  • Общее количество вершин: n-1
  • Длина критического пути: [Log2n]
  • Каноническая ширина ЯПФ: n

На рисунке изображён граф алгоритма. В данном случае выполнено суммирование 8 элементов массива. Вершины, соответствующие входным данным, обозначены октаэдром.

4 ПОСЛЕДОВАТЕЛЬНО-ПАРАЛЛЕЛЬНЫЙ МЕТОД СУММИРОВАНИЯ

XY projection
4.1 Ссылка на описание в энциклопедии AlgoWiki:

Последовательно-параллельный метод суммирования

4.2 Описание алгоритма на Algolang:

<algo>

<params>
<param name="n" type="int" value="25"></param>
<param name="p" type="int" value="5"></param>
</params>

<block id="0" dims="2">
количество процессоров
<arg name="i" val="1..p"></arg>
на каждый процессор, кроме одного, распределяется одинаковое количество
элементов массива (n/p, округленное в бОльшую сторону)
<arg name="j" val="1..n"></arg>
<arg name="j" val="1..ceil(n/p)"></arg>

сумма элементов массива, равномерно распределенных по (p-1) процессорам
<vertex condition="(j>1)and(i>1)and(j<ceil(n/p))" type="1">
<in src="i,j-1"></in>
</vertex>

сумма оставшихся эелементов
<vertex condition="(j>1)and(i=1)and(j<=(n-p-(ceil(n/p)-1)*(p-1)))" type="1">
<in src="i,j-1"></in>
</vertex>

последовательное суммирование получившихся сумм на одном из процессоров
<vertex condition="(i>2)and(j=ceil(n/p))" type="1">
<in src="i-1,j"></in>
<in src="i,j-1"></in>
</vertex>
<vertex condition="(i=2)and(j=ceil(n/p))" type="1">
<in src="i-1,n-p-(ceil(n/p)-1)*(p-1)"></in></in>
<in src="i,j-1"></in>
</vertex>
</block>

</algo>

4.3 Характеристики алгоритма (Для суммирования массива порядка n):
  • Общее количество вершин: n-1
  • Длина критического пути:
    • ceil(n/p)-1 - суммирования по частям массива (p ветвей)
    • p-1 - одна последовательная ветвь
  • Каноническая ширина ЯПФ: p

На рисунке изображён граф алгоритма без входных и выходных данных для случая суммирования 25 элементов массива на 5 процессорах.

5 Компактная схема метода Гаусса для трёхдиагональной матрицы

XY projection
5.1 Ссылка на описание в энциклопедии AlgoWiki:

Компактная схема метода Гаусса для трёхдиагональной матрицы

5.2 Описание алгоритма на Algolang:

<algo>

<params>
<param name="n" type="int" value="6"></param>
</params>

<block id="0" dims="2">
<arg name="j" val="1..n"></arg>
<arg name="i" val="1..n"></arg>

деление
<vertex condition="(i=j+1)and(j>1)" type="1">
<in src="j,j"></in>
</vertex>

вычетание
<vertex condition="(j=i)and(j>1)" type="2">
<in src="j,i-1"></in>
</vertex>

умножение
<vertex condition="j=i+1" type="3">
<in src="j-1,i+1"></in>
</vertex>
</block>

</algo>

5.3 Характеристики алгоритма (Для матрицы с рангом n):
  • Общее количество вершин: 3n-3
  • Длина критического пути:
    • n−1 ярусов делений
    • n−1 ярусов умножений
    • n−1 ярусов сложений (вычитаний)
  • Каноническая ширина ЯПФ: 1

На рисунке изображён граф алгоритма для n=6.

6 Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки

XY projection
6.1 Ссылка на описание в энциклопедии AlgoWiki:

Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки

6.2 Описание алгоритма на Algolang:

<algo>

<params>
<param name = "N" type = "int" value = "3"></param>
</params>

<block id="0" dims="2">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..2^N"></arg>

<vertex condition = "(J - 1) % (2^I) < 2^(I - 1)" type = "1">
<in src = "I - 1, J"></in>
<in src = "I - 1, J + 2^(I -1)"></in>
</vertex>

<vertex condition = "(J - 1) % (2^I) >= 2^(I - 1)" type = "2">
<in src = "I - 1, J"></in>
<in src = "I - 1, J - 2^(I - 1)"></in>
</vertex>

</block>

</algo>

6.3 Характеристики алгоритма (Для вектора с размерностью n):
  • Общее количество вершин: n*log2n
  • Длина критического пути:
    • log2n операций комплексного сложения/вычитания
    • log2n операций комплексного умножения
  • Каноническая ширина ЯПФ: n

На рисунке изображён граф алгоритма для n=8.

7 Метод Гивенса (вращений) QR-разложения квадратной матрицы

XY projection
YZ projection
XZ projection
7.1 Ссылка на описание в энциклопедии AlgoWiki:

Простой алгоритм Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный точечный вариант)

7.2 Описание алгоритма на Algolang:

<algo>

<params>
<param name="n" type="int" value="5"></param>
</params>
<block dims="3">
<arg name="k" val="1..n-1"></arg>
<arg name="i" val="1..n-1"></arg>
<arg name="j" val="1..n"></arg>
выполнение поворота 2-мерного вектора 1 яруса
<vertex condition="(j>k)and(i=k)and(k=1)" type="2">
<in src="k,i,k"></in>
</vertex>
выполнение поворота 2-мерного вектора 1 яруса
<vertex condition="(j>k)and(i>k)and(k=1)" type="2">
<in src="k,i,k"></in>
<in src="k,i-1,j"></in>
</vertex>
выполнение поворота 2-мерного вектора остальных ярусов
<vertex condition="(j>k)and(k>1)and(i=k)" type="2">
<in src="k,i,k"></in>
<in src="k-1,i,j"></in>
<in src="k-1,i-1,j"></in>
</vertex>
операция вычисления параметров поворота остальных ярусов
<vertex condition="(j=k)and(k>1)and(i=k)" type="1">
<in src="k-1,i,j"></in>
<in src="k-1,i-1,j"></in>
</vertex>
выполнение поворота 2-мерного вектора остальных ярусов
<vertex condition="(j>k)and(k>1)and(i>k)" type="2">
<in src="k,i,k"></in>
<in src="k-1,i,j"></in>
<in src="k,i-1,j"></in>
</vertex>
операция вычисления параметров поворота остальных ярусов
<vertex condition="(j=k)and(k>1)and(i>k)" type="1">
<in src="k-1,i,j"></in>
</vertex>
</block>

</algo>

7.3 Характеристики алгоритма (Для матрицы порядка n):
  • Общее количество вершин: n3/3
  • Длина критического пути:
    • 2n−3 макровершины вычисления параметров поворота
    • n−1 макровершин поворотов
  • Каноническая ширина ЯПФ: n

На рисунке изображён Граф алгоритма без отображения входных и выходных данных для n=5.

Источник — https://algowiki-project.org/w/ru/index.php?title=Библиотека_алгоритмов&oldid=28597