Участник:Lonalone/Генерация гауссовского вектора методом линейных преобразований - История изменений

Lonalone: /* Генерация случайного вектора Y */

2018-12-08T06:54:40Z

Генерация случайного вектора Y

← Предыдущая версия		Версия от 06:54, 8 декабря 2018
Строка 106:		Строка 106:
	где <math>u_j^i - </math> реализации случайной величины <math>u</math>, а <math>\kappa - </math> параметр, обеспечивающий качество приближения.		где <math>u_j^i - </math> реализации случайной величины <math>u</math>, а <math>\kappa - </math> параметр, обеспечивающий качество приближения.

	Как правило, <math>\kappa</math> берут равным 12 и считают, что для подавляющего числа практических задач обеспечивается должная точность вычислений<ref name = "VVV">Балдин К.В., Уткин В.Б. Информационные системы в экономике. — М.:Дашков и Кo, 2008. — 395 с.</ref>.		Как правило, <math>\kappa</math> берут равным <math>12</math> и считают, что для подавляющего числа практических задач обеспечивается должная точность вычислений<ref name = "VVV">Балдин К.В., Уткин В.Б. Информационные системы в экономике. — М.:Дашков и Кo, 2008. — 395 с.</ref>.

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

Lonalone: /* Ресурс параллелизма алгоритма */

2018-12-08T06:51:26Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 06:51, 8 декабря 2018
Строка 272:		Строка 272:
	* <math>n</math> ярусов умножений и сложений (в каждом из ярусов — линейное количество операций, в зависимости от яруса — от <math>1</math> до <math>n</math>)		* <math>n</math> ярусов умножений и сложений (в каждом из ярусов — линейное количество операций, в зависимости от яруса — от <math>1</math> до <math>n</math>)

	Учитывая <math>n \gg \kappa</math>, можно заключить: при классификации по высоте ЯПФ алгоритм имеет сложность <math>O(n)</math>, а при классификации по ширине — <math>O(n^2)</math>.		Учитывая <math>n \gg \kappa</math>, можно заключить: при классификации по высоте ЯПФ алгоритм имеет сложность <math>O(n)</math>, при классификации по ширине — <math>O(n^2)</math>.

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

Lonalone: /* Ресурс параллелизма алгоритма */

2018-12-08T06:48:50Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 06:48, 8 декабря 2018
Строка 272:		Строка 272:
	* <math>n</math> ярусов умножений и сложений (в каждом из ярусов — линейное количество операций, в зависимости от яруса — от <math>1</math> до <math>n</math>)		* <math>n</math> ярусов умножений и сложений (в каждом из ярусов — линейное количество операций, в зависимости от яруса — от <math>1</math> до <math>n</math>)

	~~Таким образом~~, при классификации по высоте ЯПФ алгоритм имеет сложность <math>O(n)</math>, а при классификации по ширине ~~ЯПФ~~ — <math>O(n^2)</math>.		Учитывая <math>n \gg \kappa</math>, можно заключить: при классификации по высоте ЯПФ алгоритм имеет сложность <math>O(n)</math>, а при классификации по ширине — <math>O(n^2)</math>.

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

Lonalone: /* Последовательная сложность алгоритма */

2018-12-08T06:41:57Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 06:41, 8 декабря 2018
Строка 148:		Строка 148:
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

			Для генерации гауссовского случайного вектора порядка <math>n</math> в последовательном варианте требуется:
	* <math> n(n+1) + \frac {n(n-1)(n-2)}{6} </math> (умножений)		* <math> n(n+1) + \frac {n(n-1)(n-2)}{6} </math> (умножений)
	* <math> \frac {n(n+1)}{2} + \frac {n(n-1)(n-2)}{6} </math> (вычитаний)		* <math> \frac {n(n+1)}{2} + \frac {n(n-1)(n-2)}{6} </math> (вычитаний)
	* <math> \frac {n(n-1+2\kappa)}{2} </math> (сложений)		* <math> \frac {n(n-1+2\kappa)}{2} </math> (сложений)
	* <math> \frac {n(n+3)}{2} </math> (делений)		* <math> \frac {n(n+3)}{2} </math> (делений)
	* <math> 2n </math> (~~взятия~~ квадратного корня)		* <math> 2n </math> (вычислений квадратного корня)

	<math> \frac{n}{6}\left(2n^2+9n+31+6\kappa\right) </math> - итого операций.		<math> \frac{n}{6}\left(2n^2+9n+31+6\kappa\right) </math> - итого операций.

Lonalone: /* Ресурс параллелизма алгоритма */

2018-12-08T06:37:40Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 06:37, 8 декабря 2018
Строка 265:		Строка 265:

	Для генерации <math>(n)</math> вектора <math>Y</math> в параллельном варианте требуется последовательно выполнить следующие ярусы:		Для генерации <math>(n)</math> вектора <math>Y</math> в параллельном варианте требуется последовательно выполнить следующие ярусы:
	* <math>\kappa</math> ярусов сложений (<math>n</math> ~~вычислений~~ в каждом из ярусов),		* <math>\kappa</math> ярусов сложений (<math>n</math> операций в каждом из ярусов),
	* <math>1</math> ярус вычитаний, делений, умножений, вычислений квадратного корня (<math>n, 2n, n, n</math> операций соответственно),		* <math>1</math> ярус вычитаний, делений, умножений, вычислений квадратного корня (<math>n, 2n, n, n</math> операций соответственно),

Lonalone: /* Ресурс параллелизма алгоритма */

2018-12-08T06:20:54Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 06:20, 8 декабря 2018
Строка 266:		Строка 266:
	Для генерации <math>(n)</math> вектора <math>Y</math> в параллельном варианте требуется последовательно выполнить следующие ярусы:		Для генерации <math>(n)</math> вектора <math>Y</math> в параллельном варианте требуется последовательно выполнить следующие ярусы:
	* <math>\kappa</math> ярусов сложений (<math>n</math> вычислений в каждом из ярусов),		* <math>\kappa</math> ярусов сложений (<math>n</math> вычислений в каждом из ярусов),
	* <math>1</math> ярус вычитаний, делений, умножений, вычислений квадратного корня (<math>1, 2, 1, 1</math> операций соответственно),		* <math>1</math> ярус вычитаний, делений, умножений, вычислений квадратного корня (<math>n, 2n, n, n</math> операций соответственно),

	Для вычисления <math>(n)</math> вектора <math>X</math> в параллельном варианте требуется последовательно выполнить следующие ярусы:		Для вычисления <math>(n)</math> вектора <math>X</math> в параллельном варианте требуется последовательно выполнить следующие ярусы:

Lonalone: /* Вычислительное ядро алгоритма */

2018-12-08T06:14:23Z

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

← Предыдущая версия		Версия от 06:14, 8 декабря 2018
Строка 110:		Строка 110:
	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===

	Вычислительное ядро алгоритма можно составить из множественных (всего <math>\frac{n(n−1)}{2}</math>) вычислений следующих выражений:		Вычислительное ядро алгоритма можно составить из множественных (всего <math>\frac{n(n−1)}{2}</math>) вычислений следующих выражений, включающих скалярные произведения строк матрицы:

	<math>\sigma_{ij} - \sum_{k=1}^{j-1} b_{ik} b_{jk}, \quad 1 \leqslant j \leqslant i \leqslant n</math>		<math>\sigma_{ij} - \sum_{k=1}^{j-1} b_{ik} b_{jk}, \quad 1 \leqslant j \leqslant i \leqslant n</math>

Lonalone: /* Возможные способы и особенности параллельной реализации алгоритма */

2018-12-07T22:45:49Z

Возможные способы и особенности параллельной реализации алгоритма

← Предыдущая версия		Версия от 22:45, 7 декабря 2018
Строка 324:		Строка 324:
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===

	В данной реализации алгоритма ~~использованы все ресурсы~~ параллелизма в следующих этапах:		В данной реализации алгоритма весь ресурс параллелизма использован в следующих этапах:
	* вычисление элементов матрицы <math>B</math> в рамках столбца (под диагональю),		* вычисление элементов матрицы <math>B</math> в рамках столбца (под диагональю),
	* генерация вектора <math>Y</math>,		* генерация вектора <math>Y</math>,

Lonalone: /* Возможные способы и особенности параллельной реализации алгоритма */

2018-12-07T22:36:32Z

Возможные способы и особенности параллельной реализации алгоритма

← Предыдущая версия		Версия от 22:36, 7 декабря 2018
Строка 323:		Строка 323:

	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===

			В данной реализации алгоритма использованы все ресурсы параллелизма в следующих этапах:
			* вычисление элементов матрицы <math>B</math> в рамках столбца (под диагональю),
			* генерация вектора <math>Y</math>,
			* вычисление вектора <math>X</math> (умножение матрицы на вектор, сложение векторов).

	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===

Lonalone: /* Ресурс параллелизма алгоритма */

2018-12-07T22:25:47Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 22:25, 7 декабря 2018
Строка 270:		Строка 270:
	Для вычисления <math>(n)</math> вектора <math>X</math> в параллельном варианте требуется последовательно выполнить следующие ярусы:		Для вычисления <math>(n)</math> вектора <math>X</math> в параллельном варианте требуется последовательно выполнить следующие ярусы:
	* <math>n</math> ярусов умножений и сложений (в каждом из ярусов — линейное количество операций, в зависимости от яруса — от <math>1</math> до <math>n</math>)		* <math>n</math> ярусов умножений и сложений (в каждом из ярусов — линейное количество операций, в зависимости от яруса — от <math>1</math> до <math>n</math>)

			Таким образом, при классификации по высоте ЯПФ алгоритм имеет сложность <math>O(n)</math>, а при классификации по ширине ЯПФ — <math>O(n^2)</math>.

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