Шаблон:Main page/Featured - История изменений

ASA: /* Описание свойств и структуры алгоритма */

2015-07-29T14:01:46Z

Описание свойств и структуры алгоритма

← Предыдущая версия		Версия от 14:01, 29 июля 2015
Строка 14:		Строка 14:
	\|}		\|}

	== ~~Описание свойств~~ и ~~структуры~~ алгоритма ==		== Свойства и структура алгоритма ==

	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
Строка 24:		Строка 24:
	Для разреженных матриц разложение Холецкого также широко применяется в качестве основного этапа прямого метода решения линейных систем. В этом случае используют специальные упорядочивания для уменьшения ширины профиля исключения, а следовательно и уменьшения количества арифметических операций. Другие упорядочивания используются для выделения независимых блоков вычислений при работе на системах с параллельной организацией.		Для разреженных матриц разложение Холецкого также широко применяется в качестве основного этапа прямого метода решения линейных систем. В этом случае используют специальные упорядочивания для уменьшения ширины профиля исключения, а следовательно и уменьшения количества арифметических операций. Другие упорядочивания используются для выделения независимых блоков вычислений при работе на системах с параллельной организацией.

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

	Исходные данные: положительно определённая симметрическая матрица <math>A</math> (элементы <math>a_{ij}</math>).		Исходные данные: положительно определённая симметрическая матрица <math>A</math> (элементы <math>a_{ij}</math>).

ASA в 10:37, 13 апреля 2015

2015-04-13T10:37:52Z

← Предыдущая версия		Версия от 10:37, 13 апреля 2015
Строка 43:		Строка 43:

	В ряде реализаций деление на диагональный элемент выполняется в два этапа: вычисление <math>1/l_{ii}</math> и затем умножение на него всех (видоизменённых) <math>a_{ji}</math> . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный.		В ряде реализаций деление на диагональный элемент выполняется в два этапа: вычисление <math>1/l_{ii}</math> и затем умножение на него всех (видоизменённых) <math>a_{ji}</math> . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный.

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

	~~Для разложения матрицы порядка n методом Холецкого в последовательном (наиболее быстром) варианте требуется:~~

	* <math>n</math> вычислений квадратного корня,
	* <math>\frac{n(n-1)}{2}</math> делений,
	* <math>\frac{n^3-n}{6}</math> сложений (вычитаний),
	* <math>\frac{n^3-n}{6}</math> умножений.

	~~Умножения и сложения (вычитания) составляют ''основную часть алгоритма''.~~

	При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает долю умножений и сложений/вычитаний во времени, требуемом для выполнения метода Холецкого.

	При классификации по последовательной сложности, таким образом, метод Холецкого относится к алгоритмам ''с кубической сложностью''.

	:''[[Разложение Холецкого (метод квадратного корня)\|Читать полностью…]]''		:''[[Разложение Холецкого (метод квадратного корня)\|Читать полностью…]]''

Nebaruzdin: Правка внешнего вида.

2015-03-30T00:11:14Z

Правка внешнего вида.

← Предыдущая версия		Версия от 00:11, 30 марта 2015
Строка 1:		Строка 1:
			<div style="font-size: 160%; font-weight: bold; text-align: center;">
	----		Разложение Холецкого (метод квадратного корня)
	~~<br /~~>		</div>
	~~Читать полностью: [[Разложение_Холецкого_~~(~~метод_квадратного_корня~~)~~]]<br />~~
	<br />
	~~----~~

	{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|40%}}};" cellpadding=8 cellspacing=1 border=0		{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|40%}}};" cellpadding=8 cellspacing=1 border=0
Строка 61:		Строка 58:

	При классификации по последовательной сложности, таким образом, метод Холецкого относится к алгоритмам ''с кубической сложностью''.		При классификации по последовательной сложности, таким образом, метод Холецкого относится к алгоритмам ''с кубической сложностью''.

			:''[[Разложение Холецкого (метод квадратного корня)\|Читать полностью…]]''

Nebaruzdin: Ширина врезки =40%.

2015-03-29T21:28:50Z

Ширина врезки =40%.

← Предыдущая версия		Версия от 21:28, 29 марта 2015
Строка 6:		Строка 6:
	----		----

	{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|35%}}};" cellpadding=8 cellspacing=1 border=0		{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|40%}}};" cellpadding=8 cellspacing=1 border=0
	\|-		\|-
	\|align=left width=100% style="background-color:#f3f3ff; border:1px solid"\|		\|align=left width=100% style="background-color:#f3f3ff; border:1px solid"\|

Nebaruzdin: Ширина врезки +5%.

2015-03-29T21:23:28Z

Ширина врезки +5%.

← Предыдущая версия		Версия от 21:23, 29 марта 2015
Строка 6:		Строка 6:
	----		----

	{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|30%}}};" cellpadding=8 cellspacing=1 border=0		{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|35%}}};" cellpadding=8 cellspacing=1 border=0
	\|-		\|-
	\|align=left width=100% style="background-color:#f3f3ff; border:1px solid"\|		\|align=left width=100% style="background-color:#f3f3ff; border:1px solid"\|

Nebaruzdin: Откат правок Nebaruzdin (обсуждение) к версии Algoman

2015-03-29T21:07:30Z

Откат правок Nebaruzdin (обсуждение) к версии Algoman

← Предыдущая версия		Версия от 21:07, 29 марта 2015
Строка 6:		Строка 6:
	----		----

	{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|35%}}};" cellpadding=8 cellspacing=1 border=0		{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|30%}}};" cellpadding=8 cellspacing=1 border=0
	\|-		\|-
	\|align=left width=100% style="background-color:#f3f3ff; border:1px solid"\|		\|align=left width=100% style="background-color:#f3f3ff; border:1px solid"\|

Nebaruzdin: Ширина врезки =35%.

2015-03-29T21:04:35Z

Ширина врезки =35%.

← Предыдущая версия		Версия от 21:04, 29 марта 2015
Строка 6:		Строка 6:
	----		----

	{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|40%}}};" cellpadding=8 cellspacing=1 border=0		{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|35%}}};" cellpadding=8 cellspacing=1 border=0
	\|-		\|-
	\|align=left width=100% style="background-color:#f3f3ff; border:1px solid"\|		\|align=left width=100% style="background-color:#f3f3ff; border:1px solid"\|

Nebaruzdin: Ширина врезки =40%.

2015-03-29T21:02:32Z

Ширина врезки =40%.

← Предыдущая версия		Версия от 21:02, 29 марта 2015
Строка 6:		Строка 6:
	----		----

	{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|45%}}};" cellpadding=8 cellspacing=1 border=0		{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|40%}}};" cellpadding=8 cellspacing=1 border=0
	\|-		\|-
	\|align=left width=100% style="background-color:#f3f3ff; border:1px solid"\|		\|align=left width=100% style="background-color:#f3f3ff; border:1px solid"\|

Nebaruzdin: Ширина врезки +10%.

2015-03-29T21:00:17Z

Ширина врезки +10%.

← Предыдущая версия		Версия от 21:00, 29 марта 2015
Строка 6:		Строка 6:
	----		----

	{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|35%}}};" cellpadding=8 cellspacing=1 border=0		{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|45%}}};" cellpadding=8 cellspacing=1 border=0
	\|-		\|-
	\|align=left width=100% style="background-color:#f3f3ff; border:1px solid"\|		\|align=left width=100% style="background-color:#f3f3ff; border:1px solid"\|

Nebaruzdin: Ширина врезки +5%.

2015-03-29T20:58:02Z

Ширина врезки +5%.

← Предыдущая версия		Версия от 20:58, 29 марта 2015
Строка 6:		Строка 6:
	----		----

	{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|30%}}};" cellpadding=8 cellspacing=1 border=0		{\| style="float:{{{float\|right}}}; clear:right;margin-left: 1em; width:{{{width\|35%}}};" cellpadding=8 cellspacing=1 border=0
	\|-		\|-
	\|align=left width=100% style="background-color:#f3f3ff; border:1px solid"\|		\|align=left width=100% style="background-color:#f3f3ff; border:1px solid"\|