Участник:Alexbashirov/Алгоритм Ланцоша для точной арифметики - История изменений

ASA в 13:56, 19 декабря 2016

2016-12-19T13:56:12Z

← Предыдущая версия		Версия от 13:56, 19 декабря 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|ASA\|Konshin}}
	~~{{Assignment~~\|Konshin}}

	Авторы: [[Участник: Alexbashirov\|Баширов А.Д.]]		Авторы: [[Участник: Alexbashirov\|Баширов А.Д.]]

Konshin в 18:23, 18 декабря 2016

2016-12-18T18:23:38Z

← Предыдущая версия		Версия от 18:23, 18 декабря 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment}}
			{{Assignment\|Konshin}}

	Авторы: [[Участник: Alexbashirov\|Баширов А.Д.]]		Авторы: [[Участник: Alexbashirov\|Баширов А.Д.]]

Alexbashirov в 15:40, 18 декабря 2016

2016-12-18T15:40:54Z

← Предыдущая версия		Версия от 15:40, 18 декабря 2016
Строка 1:		Строка 1:
			{{Assignment}}

	Авторы: [[Участник: Alexbashirov\|Баширов А.Д.]]		Авторы: [[Участник: Alexbashirov\|Баширов А.Д.]]

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

2016-12-18T15:37:47Z

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

← Предыдущая версия		Версия от 15:37, 18 декабря 2016
Строка 106:		Строка 106:
	Поскольку алгоритм является итерационным, то выполнять параллельные операции возможно только внутри каждой итерации алгоритма. Сами итерации выполняются в строгой последовательности и не могут быть параллелизованны. Однако внутри каждой итерации происходят два процесса, которые могут быть параллелизованны:		Поскольку алгоритм является итерационным, то выполнять параллельные операции возможно только внутри каждой итерации алгоритма. Сами итерации выполняются в строгой последовательности и не могут быть параллелизованны. Однако внутри каждой итерации происходят два процесса, которые могут быть параллелизованны:
	* умножение матрицы на вектор,		* умножение матрицы на вектор,
	* процесс поиска собственных значений.		* процесс поиска собственных значений. Этот процесс является самостоятельной задачей. Для поиска собственных значений могут использоваться различные методы, например такие, как QR-алгоритм или метод "Разделяй и властвуй". Соответственно, в зависимости от выбранного алгоритма поиска с./знач. могут иметь различные свойства.

	Умножение квадратной матрицы размерности <math>n\times n</math> на вектор размерности <math>n</math> требует <math>n</math> ярусов умножений и сложений.		Умножение квадратной матрицы размерности <math>n\times n</math> на вектор размерности <math>n</math> требует <math>n</math> ярусов умножений и сложений.

Alexbashirov: /* Масштабируемость алгоритма и его реализации */

2016-12-18T15:28:20Z

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

@@ Строка 140: / Строка 140: @@
 === Возможные способы и особенности параллельной реализации алгоритма===
 ===  Масштабируемость алгоритма и его реализации===
-'''TODO'''
-[[Файл:Lanczos_time_matrix.png|1000px|thumb|center| ]]
+Для изучения свойств масштабируемости алгоритма Ланцоша без переортогонализации былы исследованы результаты выполненных на с/к Ломоносов вычислений.
 === Динамические характеристики и эффективность реализации алгоритма===

Alexbashirov: /* Масштабируемость алгоритма и его реализации */

2016-12-18T15:10:50Z

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

← Предыдущая версия		Версия от 15:10, 18 декабря 2016
Строка 141:		Строка 141:
	=== Масштабируемость алгоритма и его реализации===		=== Масштабируемость алгоритма и его реализации===
	'''TODO'''		'''TODO'''
			[[Файл:Lanczos_time_matrix.png\|1000px\|thumb\|center\| ]]

	=== Динамические характеристики и эффективность реализации алгоритма===		=== Динамические характеристики и эффективность реализации алгоритма===

Alexbashirov: /* Схема последовательной реализации алгоритма */

2016-12-17T20:18:58Z

Схема последовательной реализации алгоритма

← Предыдущая версия		Версия от 20:18, 17 декабря 2016
Строка 46:		Строка 46:
	<math>q=b/\|\|b\|\|_2</math>, <math>\beta_0=0</math>, <math>q_0=0</math>		<math>q=b/\|\|b\|\|_2</math>, <math>\beta_0=0</math>, <math>q_0=0</math>

	<math> ~ {\rm for} j=1 ~ {\rm to} k</math>		<math> ~ {\rm for } j=1 ~ {\rm to} k</math>

	<math>z = Aq_j</math>		<math>z = Aq_j</math>
Строка 62:		Строка 62:
	Вычисление собственных значений и векторов матрицы <math>T_j</math>		Вычисление собственных значений и векторов матрицы <math>T_j</math>

	<math> ~ {\rm end for} </math>		<math> ~ {\rm end} ~ {\rm for} </math>

Alexbashirov: /* Схема последовательной реализации алгоритма */

2016-12-17T20:18:29Z

Схема последовательной реализации алгоритма

← Предыдущая версия		Версия от 20:18, 17 декабря 2016
Строка 46:		Строка 46:
	<math>q=b/\|\|b\|\|_2</math>, <math>\beta_0=0</math>, <math>q_0=0</math>		<math>q=b/\|\|b\|\|_2</math>, <math>\beta_0=0</math>, <math>q_0=0</math>

	<math> for j=1 to k</math>		<math> ~ {\rm for} j=1 ~ {\rm to} k</math>

	<math>z = Aq_j</math>		<math>z = Aq_j</math>
Строка 56:		Строка 56:
	<math> \beta_j = \|\|z\|\|_2</math>		<math> \beta_j = \|\|z\|\|_2</math>

	<math> if \beta_j = 0 ~ {\rm quit}</math>		<math> ~ {\rm if} \beta_j = 0 ~ {\rm quit}</math>

	<math> q_{j+1} = z/\beta_j</math>		<math> q_{j+1} = z/\beta_j</math>
Строка 62:		Строка 62:
	Вычисление собственных значений и векторов матрицы <math>T_j</math>		Вычисление собственных значений и векторов матрицы <math>T_j</math>

	<math> end for </math>		<math> ~ {\rm end for} </math>

Konshin: /* Схема последовательной реализации алгоритма */

2016-12-08T11:04:28Z

Схема последовательной реализации алгоритма

← Предыдущая версия		Версия от 11:04, 8 декабря 2016
Строка 56:		Строка 56:
	<math> \beta_j = \|\|z\|\|_2</math>		<math> \beta_j = \|\|z\|\|_2</math>

	<math> if \beta_j = 0 quit</math>		<math> if \beta_j = 0 ~ {\rm quit}</math>

	<math> q_{j+1} = z/\beta_j</math>		<math> q_{j+1} = z/\beta_j</math>

Alexbashirov: /* Информационный граф */

2016-12-03T20:57:53Z

Информационный граф

← Предыдущая версия		Версия от 20:57, 3 декабря 2016
Строка 90:		Строка 90:
	=== Информационный граф ===		=== Информационный граф ===
	В данном разделе представлен информационный граф алгоритма, дающий представление о переходе от одной итерации к другой.		В данном разделе представлен информационный граф алгоритма, дающий представление о переходе от одной итерации к другой.

			Схема состоит из трех частей, каждая из которых символизирует свой итерационный слой.
			Первый и второй слои являются стартовыми - на них задаются начальные приближенные значения параметров, с которыми алгоритм может быть запущен. Далее работа с уточнением значений этих параметров идет в рамках итерационного цикла на третьем слое. Такие входные данные, как матрица оператора <math>A</math> используются на каждом итерационном слое, поэтому обозначена как входные данные на втором и третьем слоях на схеме.
			Те данные, которые передаются на следущий итерационный слой с предыдущего - обозначены стрелками между вторым и третьим слоями.

	[[Файл:Информационный_граф_1.png\|1000px\|thumb\|center\| <math>\|\|x\|\|</math> - операция вычисления нормы;		[[Файл:Информационный_граф_1.png\|1000px\|thumb\|center\| <math>\|\|x\|\|</math> - операция вычисления нормы;