Классический метод ортогонализации - История изменений

ASA в 05:47, 9 июля 2022

2022-07-09T05:47:26Z

← Предыдущая версия		Версия от 05:47, 9 июля 2022
Строка 205:		Строка 205:

	Процесс Грама ― Шмидта может быть истолкован как разложение невырожденной квадратной матрицы в произведение ортогональной (или унитарной матрицы в случае эрмитова пространства) и верхнетреугольной матрицы с положительными диагональными элементами ― QR-разложение, что есть частный случай разложения Ивасавы.		Процесс Грама ― Шмидта может быть истолкован как разложение невырожденной квадратной матрицы в произведение ортогональной (или унитарной матрицы в случае эрмитова пространства) и верхнетреугольной матрицы с положительными диагональными элементами ― QR-разложение, что есть частный случай разложения Ивасавы.

			== Программная реализация алгоритма ==
			=== Особенности реализации последовательного алгоритма ===
			=== Возможные способы и особенности параллельной реализации алгоритма ===
			=== Результаты прогонов ===
			=== Выводы для классов архитектур ===
			== Литература ==

			<references />

	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]

	[[en:Classical orthogonalization method]]		[[en:Classical orthogonalization method]]

ASA в 12:00, 14 марта 2018

2018-03-14T12:00:07Z

← Предыдущая версия		Версия от 12:00, 14 марта 2018
Строка 205:		Строка 205:

	Процесс Грама ― Шмидта может быть истолкован как разложение невырожденной квадратной матрицы в произведение ортогональной (или унитарной матрицы в случае эрмитова пространства) и верхнетреугольной матрицы с положительными диагональными элементами ― QR-разложение, что есть частный случай разложения Ивасавы.		Процесс Грама ― Шмидта может быть истолкован как разложение невырожденной квадратной матрицы в произведение ортогональной (или унитарной матрицы в случае эрмитова пространства) и верхнетреугольной матрицы с положительными диагональными элементами ― QR-разложение, что есть частный случай разложения Ивасавы.

			[[Категория:Статьи в работе]]

			[[en:Classical orthogonalization method]]

Frolov в 12:33, 20 января 2018

2018-01-20T12:33:10Z

← Предыдущая версия		Версия от 12:33, 20 января 2018
Строка 7:		Строка 7:
	\| output_data = <math>3N^2/2</math>		\| output_data = <math>3N^2/2</math>
	}}		}}

			Основные авторы описания: [[Участник:DVIN\|Инжелевская Дарья Валерьевна]] (свойства и структура алгоритмов), [[Участник:Frolov\|А.В.Фролов]](общая редактура текста)

	== Свойства и структура алгоритмов ==		== Свойства и структура алгоритмов ==

Frolov в 12:29, 20 января 2018

2018-01-20T12:29:29Z

← Предыдущая версия		Версия от 12:29, 20 января 2018
Строка 2:		Строка 2:
	\| name = Классическая ортогонализация Грама-Шмидта		\| name = Классическая ортогонализация Грама-Шмидта
	\| serial_complexity = <math>O(N^3)</math>		\| serial_complexity = <math>O(N^3)</math>
	\| pf_height = <math>O(N)</math>		\| pf_height = <math>O(N^2)</math>
	\| pf_width = <math>O(N^2)</math>		\| pf_width = <math>O(N)</math>
	\| input_data = <math>N^2</math>		\| input_data = <math>N^2</math>
	\| output_data = <math>3N^2/2</math>		\| output_data = <math>3N^2/2</math>
Строка 169:		Строка 169:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	В параллельном варианте, в отличие от последовательного, вычисления <math>\mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i}</math> можно выполнять параллельно. То есть после каждого вычисления <math>b_j</math> можно запускать параллельное вычисление <math>\mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i}</math> для всех <math>i=j+1..N</math>. Кроме того можно параллельно производить вычитание соответствующего <math>\mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i}</math> для всех <math>i=j+1..N</math>.		В параллельном варианте, в отличие от последовательного, можно параллельно производить вычитание соответствующего <math>\mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i}</math> для всех <math>i=j+1..N</math>. Параллельное же вычисление проекций соответствует другому алгоритму.

	~~Для ортогонализации в параллельном варианте требуется последовательно выполнить следующие ярусы:~~		При классификации по высоте (количество ярусов в ЯПФ ) ЯПФ, таким образом, ортогонализация Грамма-Шмидта относится к алгоритмам со сложностью <math>O(N^2)</math>.
	* <math>N</math> ярусов в каждом из которых будет выполнятся,
	* по ~~<math>N - 1</math> операторов проекций~~ (~~в каждом из~~ ярусов ~~линейное количество проекций,~~ в ~~зависимости от яруса — от <math>N-1</math> до <math>1</math>~~),
	* по <math>N - 1</math> ~~сложений~~ (~~в каждом из ярусов линейное количество сложений, в зависимости от яруса — от <math>~~N~~-1</math> до <math>1~~</math>),

	При классификации по высоте (количество ярусов в ЯПФ ) ЯПФ, таким образом, ортогонализация Грамма-Шмидта относится к алгоритмам со сложностью <math>O(N)</math>.		При классификации по ширине (максимальное количество вершин в ярусе) ЯПФ его сложность будет <math>O(N)</math>.

	При классификации по ширине (максимальное количество вершин в ярусе) ЯПФ его сложность будет <math>O(N^2)</math>.

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

Frolov: /* Математическое описание алгоритма */

2018-01-20T12:23:42Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 12:23, 20 января 2018
Строка 35:		Строка 35:


	На основе каждого вектора <math>\mathbf{b}_j \;(j = 1 \ldots N)</math> может быть получен нормированный вектор: <math>\mathbf{e}_j = {\mathbf{b}_j\over \\|\\| \mathbf{b}_j \\|\\|_2}</math> (у нормированного вектора направление будет таким же, как у исходного, а длина — единичной).		На основе каждого вектора <math>\mathbf{b}_j \;(j = 1 \ldots N)</math> может быть получен нормированный вектор: <math>\mathbf{e}_j = {\mathbf{b}_j\over \\| \mathbf{b}_j \\|_2}</math> (у нормированного вектора направление будет таким же, как у исходного, а длина — единичной).

	Результаты процесса Грама — Шмидта:		Результаты процесса Грама — Шмидта:
Строка 42:		Строка 42:

	<math>\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N</math> — система ортонормированных векторов.		<math>\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N</math> — система ортонормированных векторов.


	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===

Frolov: /* Свойства и структура алгоритмов */

2018-01-20T12:23:05Z

Свойства и структура алгоритмов

Внесённые изменения

Frolov в 12:06, 20 января 2018

2018-01-20T12:06:11Z

Внесённые изменения

Frolov: Frolov переименовал страницу Классический метод ортогонализации QR-разложения квадратной матрицы (вещественный вариант) в [[Классический…

2017-05-13T15:22:11Z

Frolov переименовал страницу Классический метод ортогонализации QR-разложения квадратной матрицы (вещественный вариант) в [[Классический…

← Предыдущая версия	Версия от 15:22, 13 мая 2017
(нет различий)

Frolov: Новая страница: «{{algorithm | name = Классическая ортогонализация Грама-Шмидта | serial_complexity = $O(N^3)$ | pf_h…»

2017-05-04T11:38:26Z

Новая страница: «{{algorithm | name = Классическая ортогонализация Грама-Шмидта | serial_complexity = <math>O(N^3)</math> | pf_h…»

Новая страница

{{algorithm
| name = Классическая ортогонализация Грама-Шмидта
| serial_complexity = <math>O(N^3)</math>
| pf_height = <math>O(N)</math>
| pf_width = <math>O(N^2)</math>
| input_data = <math>N^2</math>
| output_data = <math>3N^2/2</math>
}}