Участник:KibAndrey/Ортогонализация Грама-Шмидта - История изменений

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

2017-09-14T07:04:31Z

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

← Предыдущая версия		Версия от 07:04, 14 сентября 2017
Строка 214:		Строка 214:
	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	Для построения ортонормированного базиса методом Грама–Шмидта необходимо выполнить следующие ярусы операций:		Для построения ортонормированного базиса методом Грама–Шмидта необходимо выполнить следующие ярусы операций:
	*<math>k</math> ярусов вычисления скалярных произведений векторов на самих себя (по одной операций на каждом, сложность операции по высоте и по ширине [[глоссарий#Ярусно-параллельная форма графа алгоритма\|ЯПФ]] — O(n) и O(1) соответственно);		*<math>k</math> ярусов вычисления скалярных произведений векторов на самих себя (по одной операций на каждом, сложность операции по высоте и по ширине [[глоссарий#Ярусно-параллельная форма графа алгоритма\|ЯПФ]] — <math>O(n)</math> и <math>O(1)</math> соответственно);
	*<math>k</math> ярусов вычисления квадратного корня (по одной операции на каждом);		*<math>k</math> ярусов вычисления квадратного корня (по одной операции на каждом);
	*<math>k</math> ярусов деления (по <math>n</math> операций на каждом);		*<math>k</math> ярусов деления (по <math>n</math> операций на каждом);

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

2017-09-14T06:59:46Z

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

← Предыдущая версия		Версия от 06:59, 14 сентября 2017
Строка 259:		Строка 259:
	== Возможные способы и особенности параллельной реализации алгоритма ==		== Возможные способы и особенности параллельной реализации алгоритма ==

	Анализ последовательной реализации алгоритма Грама-Шмидта с помощью инструмента [http://valgrind.org/docs/manual/cl-manual.html callgrind] показывает, что наибольшую долю <math>\big(</math>		Анализ последовательной реализации алгоритма Грама-Шмидта с помощью инструмента [http://valgrind.org/docs/manual/cl-manual.html callgrind] показывает, что наибольшую долю <math>\big(</math>более 97% для <math>k=n=512\big)</math> процессорного времени использует процесс вычитания проекций нормированного вектора от остальных векторов. Этот процесс состоит из вложенных циклов - в одном из циклов происходит итерация по векторам, а в другом — по подпространствам. Таким образом, задача допускает следующие варианты параллельных реализаций:
	более 97% для <math>k=n=512\big)</math> процессорного времени использует процесс вычитания проекций нормированного вектора от остальных векторов. Этот процесс состоит из вложенных циклов - в одном из циклов происходит итерация по векторам, а в другом — по подпространствам. Таким образом, задача допускает следующие варианты параллельных реализаций:
	* Распараллеливание по векторам.		* Распараллеливание по векторам.
	Векторы распределяются по MPI-процессам. После нормировки очередного вектора процесс рассылает его остальным с помощью процедур групповой коммуникации. В исследуемой реализации используется вызов MPI_Bcast.		Векторы распределяются по MPI-процессам. После нормировки очередного вектора процесс рассылает его остальным с помощью процедур групповой коммуникации. В исследуемой реализации используется вызов MPI_Bcast.

Amelie: /* Макроструктура алгоритма */

2017-09-14T06:58:27Z

Макроструктура алгоритма

← Предыдущая версия		Версия от 06:58, 14 сентября 2017
Строка 113:		Строка 113:
	::<math>\mathbf{q_{1}}= \frac{\mathbf{a_{1}}}{\left\|\mathbf{a_1}\right\|}</math>.		::<math>\mathbf{q_{1}}= \frac{\mathbf{a_{1}}}{\left\|\mathbf{a_1}\right\|}</math>.

	2. При <math>i=2,...,k</math>		2. При <math>i=2,...,k</math>:
	::<math>\mathbf{b_{i}}=\mathbf{a_{i}}-\sum\limits_{k=1}^{i-1}(\mathbf{a_i},\mathbf{q_k})\mathbf{q_{k}}</math>		::<math>\mathbf{b_{i}}=\mathbf{a_{i}}-\sum\limits_{k=1}^{i-1}(\mathbf{a_i},\mathbf{q_k})\mathbf{q_{k}}</math>

Amelie: /* Общее описание алгоритма */

2017-09-14T06:57:07Z

Общее описание алгоритма

← Предыдущая версия		Версия от 06:57, 14 сентября 2017
Строка 31:		Строка 31:

	Процесс ортоганализации Грама-Шмидта лежит в основе многих алгоритмов вычислительной математики.		Процесс ортоганализации Грама-Шмидта лежит в основе многих алгоритмов вычислительной математики.
	Классический процесс ортогонализации Грама–Шмидта применяется в таких ~~совменных~~ областях науки, как анализ изображений<ref>Nussbaum S., Menz G. Object-based image analysis and treaty verification: new approaches in remote sensing-applied to nuclear facilities in Iran. — Springer Science & Business Media, 2008 — pp 75–81.</ref>, цифровая обработка сигналов<ref>Gopi E. S. Algorithm collections for digital signal processing applications using matlab. — Springer Science & Business Media, 2007.</ref>, нейронные сети<ref>[http://thirdworld.nl/application-of-sequential-learning-neural-networks-to-civil-engineering-modeling-problems Rajasekaran S., Suresh D., Pai G. A. V. Application of sequential learning neural networks to civil engineering modeling problems.] — ''Engineering with Computers.'' — 2002. — Т. 18. — №. 2. — pp. 138–147.</ref>.		Классический процесс ортогонализации Грама–Шмидта применяется в таких современных областях науки, как анализ изображений<ref>Nussbaum S., Menz G. Object-based image analysis and treaty verification: new approaches in remote sensing-applied to nuclear facilities in Iran. — Springer Science & Business Media, 2008 — pp 75–81.</ref>, цифровая обработка сигналов<ref>Gopi E. S. Algorithm collections for digital signal processing applications using matlab. — Springer Science & Business Media, 2007.</ref>, нейронные сети<ref>[http://thirdworld.nl/application-of-sequential-learning-neural-networks-to-civil-engineering-modeling-problems Rajasekaran S., Suresh D., Pai G. A. V. Application of sequential learning neural networks to civil engineering modeling problems.] — ''Engineering with Computers.'' — 2002. — Т. 18. — №. 2. — pp. 138–147.</ref>.

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

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

2017-09-13T21:24:35Z

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

← Предыдущая версия		Версия от 21:24, 13 сентября 2017
Строка 52:		Строка 52:
	\mathbf{b_{1}} & =\mathbf{a_{1}}, \\		\mathbf{b_{1}} & =\mathbf{a_{1}}, \\
	\mathbf{b_{2}}& =\mathbf{a_{2}}-\mathbf{b_{1}} proj_{\mathbf{b_1}}\mathbf{a_{2}},\\		\mathbf{b_{2}}& =\mathbf{a_{2}}-\mathbf{b_{1}} proj_{\mathbf{b_1}}\mathbf{a_{2}},\\

	& ...\\		& ...\\
	\mathbf{b_{i}} & =\mathbf{ a_{i}}-\sum\limits_{j=1}^{i-1}\mathbf{b_{i}} proj_{\mathbf{b_j}}\mathbf{a_{i}}.\\		\mathbf{b_{i}} & =\mathbf{ a_{i}}-\sum\limits_{j=1}^{i-1}\mathbf{b_{i}} proj_{\mathbf{b_j}}\mathbf{a_{i}}.\\

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

2017-09-13T21:23:29Z

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

← Предыдущая версия		Версия от 21:23, 13 сентября 2017
Строка 35:		Строка 35:
	== Математическое описание алгоритма ==		== Математическое описание алгоритма ==

	Пусть <math>V</math> -- евклидово пространство размерности <math>n</math>.		Пусть <math>V</math> — евклидово пространство размерности <math>n</math>.

	'''Bходные данные:'''		'''Bходные данные:'''

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

2017-09-13T21:22:58Z

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

← Предыдущая версия		Версия от 21:22, 13 сентября 2017
Строка 35:		Строка 35:
	== Математическое описание алгоритма ==		== Математическое описание алгоритма ==

	Пусть <math>V</math> --- евклидово пространство размерности <math>n</math>.		Пусть <math>V</math> -- евклидово пространство размерности <math>n</math>.

	'''Bходные данные:'''		'''Bходные данные:'''

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

2017-09-13T21:22:43Z

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

← Предыдущая версия		Версия от 21:22, 13 сентября 2017
Строка 35:		Строка 35:
	== Математическое описание алгоритма ==		== Математическое описание алгоритма ==

	Пусть <math>V</math> евклидово пространство размерности <math>n</math>.		Пусть <math>V</math> --- евклидово пространство размерности <math>n</math>.

	'''Bходные данные:'''		'''Bходные данные:'''

Amelie в 21:22, 13 сентября 2017

2017-09-13T21:22:07Z

← Предыдущая версия		Версия от 21:22, 13 сентября 2017
Строка 27:		Строка 27:

	Исторически это первый алгоритм, описывающий процесс ортогонализации. Традиционно его связывают с именами [https://en.wikipedia.org/wiki/J%C3%B8rgen_Pedersen_Gram Йоргена Педерсена Грама] и [https://en.wikipedia.org/wiki/Erhard_Schmidt Эрхарда Шмидта]. Йорган Педерсен Грам<ref name="multiple">Meyer C. D. Matrix analysis and applied linear algebra. — Siam, 2000. — Т.2.</ref> был датским актуарием (специалистом по страховой математике, на современном языке это профессия финансового аналитика), который в неявном виде представил суть процесса ортогонализации в 1883 году<ref>[http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002158604&physid=PHYS_0047 Gram J. P. Ueber die Entwickelung reeller Functionen in Reihen mittelst der Methode der kleinsten Quadrate.] — ''Journal für die reine und angewandte Mathematik.'' — 1883. — Т. 94. — pp. 41–73.</ref>. Нельзя не сказать о том, что метод ортогонализации в несколько ином, модифицированом виде, ранее использовал [https://en.wikipedia.org/wiki/Pierre-Simon_Laplace Пьер-Симон Лаплас] при нахождении массы Сатурна и Юпитера из систем нормальных уравнений и расчете распределения ошибок при этих вычислениях<ref> [https://books.google.ru/books?id=fjAVAAAAQAAJ&printsec=frontcover&hl=ru&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false Marquis de Laplace P. S. Théorie analytique des probabilités.] — V. Courcier, 1820.</ref>. Ясно, что Й. Грам не знал о том, что Лаплас ранее использовал этот метод. Эрхард Шмидт<ref name="multiple">Meyer C. D. Matrix analysis and applied linear algebra. — Siam, 2000. — Т.2.</ref> был учеником великих математиков [https://en.wikipedia.org/wiki/Hermann_Schwarz Германа Шварца] и [https://en.wikipedia.org/wiki/David_Hilbert Давида Гильберта]. Алгоритм ортогонализации был опубликован Э. Шмидтом в 1907 году в его исследовании интегральных уравнений<ref name=Shmidt>Erchard Shmidt. Mathematische Annalen Zur Theorie der linearen und nichtlinearen Integralgleichungen, 1. Teil: Entwicklung willkürlicher		Исторически это первый алгоритм, описывающий процесс ортогонализации. Традиционно его связывают с именами [https://en.wikipedia.org/wiki/J%C3%B8rgen_Pedersen_Gram Йоргена Педерсена Грама] и [https://en.wikipedia.org/wiki/Erhard_Schmidt Эрхарда Шмидта]. Йорган Педерсен Грам<ref name="multiple">Meyer C. D. Matrix analysis and applied linear algebra. — Siam, 2000. — Т.2.</ref> был датским актуарием (специалистом по страховой математике, на современном языке это профессия финансового аналитика), который в неявном виде представил суть процесса ортогонализации в 1883 году<ref>[http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002158604&physid=PHYS_0047 Gram J. P. Ueber die Entwickelung reeller Functionen in Reihen mittelst der Methode der kleinsten Quadrate.] — ''Journal für die reine und angewandte Mathematik.'' — 1883. — Т. 94. — pp. 41–73.</ref>. Нельзя не сказать о том, что метод ортогонализации в несколько ином, модифицированом виде, ранее использовал [https://en.wikipedia.org/wiki/Pierre-Simon_Laplace Пьер-Симон Лаплас] при нахождении массы Сатурна и Юпитера из систем нормальных уравнений и расчете распределения ошибок при этих вычислениях<ref> [https://books.google.ru/books?id=fjAVAAAAQAAJ&printsec=frontcover&hl=ru&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false Marquis de Laplace P. S. Théorie analytique des probabilités.] — V. Courcier, 1820.</ref>. Ясно, что Й. Грам не знал о том, что Лаплас ранее использовал этот метод. Эрхард Шмидт<ref name="multiple">Meyer C. D. Matrix analysis and applied linear algebra. — Siam, 2000. — Т.2.</ref> был учеником великих математиков [https://en.wikipedia.org/wiki/Hermann_Schwarz Германа Шварца] и [https://en.wikipedia.org/wiki/David_Hilbert Давида Гильберта]. Алгоритм ортогонализации был опубликован Э. Шмидтом в 1907 году в его исследовании интегральных уравнений<ref name=Shmidt>Erchard Shmidt. Mathematische Annalen Zur Theorie der linearen und nichtlinearen Integralgleichungen, 1. Teil: Entwicklung willkürlicher
	Funktionen nach Systemen vorgeschriebener. — Mathematische Annalen. — 1908. — V. 65. — №. 3. — pp. 370-399.</ref>, которое в свою очередь дало основание для развития теории гильбертовых пространств. Шмидт ~~использовал~~ процесс ортогонализации применительно к геометрии гильбертова пространства решений интегральных уравнений отмечал, что процесс ортогонализации принципиально такой же, какой прежде использовал Й. Грам. В отечественной литературе иногда этот процесс называют ''ортогонализацией Сонина–Шмидта''<ref>Краснов М.Л. Интегральные уравнения. Введение в теорию. — М.: Наука, 1975. — 302 с.</ref><ref>Марченко В.А. Введение в теорию обратных задач спектрального анализа. — Харьков: Акта, 2005. — 143 с.</ref>. Это название связано с тем, что разработанный Сониным<ref>О некоторых неравенствах, относящихся к определенным интегралам. Записки Академии наук по физико-математическому отделению. Серия 8. Т. 6 № 6. — C. 1–53.</ref> метод ортогонализации системы функций для частного случая по существу не отличается от метода ортогонализации системы функций, предложенного ранее Шмидтом<ref name=Shmidt>Erchard Shmidt. Mathematische Annalen Zur Theorie der linearen und nichtlinearen Integralgleichungen, 1. Teil: Entwicklung willkürlicher		Funktionen nach Systemen vorgeschriebener. — Mathematische Annalen. — 1908. — V. 65. — №. 3. — pp. 370-399.</ref>, которое в свою очередь дало основание для развития теории гильбертовых пространств. Шмидт, используя процесс ортогонализации применительно к геометрии гильбертова пространства решений интегральных уравнений, отмечал, что процесс ортогонализации принципиально такой же, какой прежде использовал Й. Грам. В отечественной литературе иногда этот процесс называют ''ортогонализацией Сонина–Шмидта''<ref>Краснов М.Л. Интегральные уравнения. Введение в теорию. — М.: Наука, 1975. — 302 с.</ref><ref>Марченко В.А. Введение в теорию обратных задач спектрального анализа. — Харьков: Акта, 2005. — 143 с.</ref>. Это название связано с тем, что разработанный Сониным<ref>О некоторых неравенствах, относящихся к определенным интегралам. Записки Академии наук по физико-математическому отделению. Серия 8. Т. 6 № 6. — C. 1–53.</ref> метод ортогонализации системы функций для частного случая по существу не отличается от метода ортогонализации системы функций, предложенного ранее Шмидтом<ref name=Shmidt>Erchard Shmidt. Mathematische Annalen Zur Theorie der linearen und nichtlinearen Integralgleichungen, 1. Teil: Entwicklung willkürlicher
	Funktionen nach Systemen vorgeschriebener. — Mathematische Annalen, 63 (1907), pp. 433–476.</ref>.		Funktionen nach Systemen vorgeschriebener. — Mathematische Annalen, 63 (1907), pp. 433–476.</ref>.

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

2016-12-19T09:33:14Z

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

← Предыдущая версия		Версия от 09:33, 19 декабря 2016
Строка 259:		Строка 259:

	Анализ последовательной реализации алгоритма Грама-Шмидта с помощью инструмента [http://valgrind.org/docs/manual/cl-manual.html callgrind] показывает, что наибольшую долю <math>\big(</math>		Анализ последовательной реализации алгоритма Грама-Шмидта с помощью инструмента [http://valgrind.org/docs/manual/cl-manual.html callgrind] показывает, что наибольшую долю <math>\big(</math>
	более 97% для <math>k=n=512\big)</math> процессорного времени использует процесс вычитания проекций нормированного вектора от остальных векторов. Этот процесс состоит из вложенных циклов - в одном из циклов происходит итерация по векторам, а в другом - по подпространствам. Таким образом, задача допускает следующие варианты параллельных реализаций:		более 97% для <math>k=n=512\big)</math> процессорного времени использует процесс вычитания проекций нормированного вектора от остальных векторов. Этот процесс состоит из вложенных циклов - в одном из циклов происходит итерация по векторам, а в другом — по подпространствам. Таким образом, задача допускает следующие варианты параллельных реализаций:
	* Распараллеливание по векторам.		* Распараллеливание по векторам.
	Векторы распределяются по MPI-процессам. После нормировки очередного вектора процесс рассылает его остальным с помощью процедур групповой коммуникации. В исследуемой реализации используется вызов MPI_Bcast.		Векторы распределяются по MPI-процессам. После нормировки очередного вектора процесс рассылает его остальным с помощью процедур групповой коммуникации. В исследуемой реализации используется вызов MPI_Bcast.