Обсуждение участника:Alexander34396: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показаны 3 промежуточные версии этого же участника)
Строка 43: Строка 43:
  
 
'''...нахождение взвешенной суммы векторов.''' Линейная комбинация векторов?
 
'''...нахождение взвешенной суммы векторов.''' Линейная комбинация векторов?
 +
 +
* Взвешенная сумма векторов - это линейная комбинация векторов
 +
  
 
'''Поэтому при увеличении эффективности использования вычислительных ресурсов и ресурсов памяти вычислительной машины при выполнении этих операций повышается эффективность метода в целом. Достигается это применением при выполнении перечисленных операций аппарата параллельных вычислений.'''
 
'''Поэтому при увеличении эффективности использования вычислительных ресурсов и ресурсов памяти вычислительной машины при выполнении этих операций повышается эффективность метода в целом. Достигается это применением при выполнении перечисленных операций аппарата параллельных вычислений.'''
  
 
Этот абзац не понятен и его нужно переформулировать. Например, применение параллельных вычислений не обязательно приводит к эффективности использованию вычислительных ресурсов.
 
Этот абзац не понятен и его нужно переформулировать. Например, применение параллельных вычислений не обязательно приводит к эффективности использованию вычислительных ресурсов.
 +
 +
* этот абзац поправил
  
  
Строка 52: Строка 57:
  
 
Почему данный подход является «наиболее рациональным»? Например, n (размер вектора) может быть очень большим и вектор не будет помещаться в память одного процессора.
 
Почему данный подход является «наиболее рациональным»? Например, n (размер вектора) может быть очень большим и вектор не будет помещаться в память одного процессора.
 +
 +
* этот подход здесь рассматрвиается как один из возможных - и в зависимости от размера входных данных и от вычислительной машины и процессора можно применять разные методы распределения входных данных
  
  
Строка 58: Строка 65:
 
Требуются ли сборки данных в таком подходе на каждой итерации метода?
 
Требуются ли сборки данных в таком подходе на каждой итерации метода?
  
 +
* Сбор данных потребуется на каждой итерации метода
  
 
== Пункт 1.10 ==
 
== Пункт 1.10 ==
Строка 65: Строка 73:
  
 
Будет просто сходиться с некоторой точностью, или в точной арифметике – это прямой метод за n шагов?
 
Будет просто сходиться с некоторой точностью, или в точной арифметике – это прямой метод за n шагов?
 +
 +
* Хотя GMRES используется как итерационный метод - теоретически он является прямым: реализуемый в точной арифметике, он приводит к точному решению системы порядка <math>n</math> не более, чем в <math>n</math> шагов
  
 
'''Существуют примеры, для которых метод застаивается и сходимость есть только на <math>m</math>-м шаге. Для таких систем, любой выбор <math> m </math> меньше, чем <math> n </math> - не сходится.'''
 
'''Существуют примеры, для которых метод застаивается и сходимость есть только на <math>m</math>-м шаге. Для таких систем, любой выбор <math> m </math> меньше, чем <math> n </math> - не сходится.'''
Строка 70: Строка 80:
 
Т.е. за n-1 шагов ошибка может быть сколь угодно большой? Нужно привести пример, ссылку или пояснить – в каком случае метод не сходится менее чем за n шагов?
 
Т.е. за n-1 шагов ошибка может быть сколь угодно большой? Нужно привести пример, ссылку или пояснить – в каком случае метод не сходится менее чем за n шагов?
  
Опечатка - '''включает в себя чрезмерную работы'''
+
* ошибка в таком случае будет больше, чем приемлемая и сходимости, соответственно, не будет; примеров на данный случай к сожалению не смог найти
 +
 
  
 +
Опечатка - '''включает в себя чрезмерную работы'''
 +
 +
* опечатку поправил
  
 
== Пункт 2.4 ==
 
== Пункт 2.4 ==
Строка 86: Строка 100:
  
  
 
+
* самостоятельно данная реализация не запускалась. в других статьях по этой теме есть результаты запуска реализации, взятой с GitHub, с использованием библиотеки MPI. так как из всех статей по одной теме далее будет собираться одна большая, содержащая результаты всех статей, то я решил поискать работы по данному методу, в том числе иностранных научных исследователей, где использовались другие библиотеки, в частности PETSc. код, используемый при запуске, так же можно найти на GitHub, как и реализации метода при помощи других библиотек (в статьях других студентов). в указанных в списке используемой литературы статьях (для данной темы нашлись статьи, в которых использовались предобуславливатели, и поэтому здесь указан график для преобусловленного метода) описаны также задачи, на которых можно применять данный метод и структуры матриц, которые соответствуют системам уравнений. точность метода, то есть допустимая ошибка, равна 1E-6. Про время явно в этих статьях не указано, но в других работах (не совсем подходящих для данной статьи), видел указание, что время замерялось полное, то есть с учетом затрат временных ресурсов на сборку векторов, кроме того в библиотеке PETSc можно обращаться к часам явно через команды PetscLogDouble time; и PetscGetTime(&time);CHKERRQ(ierr). насчет размера системы - в статье указано, что решается линейная система, полученная из дискритезации уравнения Гельмгольца (то есть берется трехмерная сетка с определенным шагом и в каждой точке сетки фиксируют значения) - берется суперклетка размером 3х3х3 и периодически повторяется вдоль одной из осей с факторами 1, 2, 3, 8, 16; в суперклетках равномерно от идеальных позиций распределены атомы, для которых как раз решается система уравнений (7a)-(7b), указанная в статье. размер системы здесь - это получается количество атомов в этих суперклетках.
 
 
 
 
 
----
 
----
  

Текущая версия на 12:02, 19 декабря 2016

--Evgeny Mortikov (обсуждение) 05:42, 2 декабря 2016 (MSK) К вашей работе есть несколько замечаний по содержанию и вопросы по пункту с масштабируемостью. Новая серия замечаний стоит с моей подписью.



1 Пункт 1.2.3

--Evgeny Mortikov (обсуждение) 05:42, 2 декабря 2016 (MSK)

вычислить [math] r_m [/math] и остановиться,если требуемая точность была достигнута, иначе повторить.

Как здесь предлагается оценивать достижение требуемой точности?


2 Пункт 1.4

--Evgeny Mortikov (обсуждение) 05:42, 2 декабря 2016 (MSK)

Умножение вектора на скаляр;

Деление вектора на скаляр.

В чем с вычислительной точки зрения принципиальная разница между умножением и делением вектора на скаляр? Деление всегда можно записать в виде умножение на обратную величину.


3 Пункт 1.5

--Evgeny Mortikov (обсуждение) 05:42, 2 декабря 2016 (MSK)

На практике используется перезапускаемая версия метода - GMRES(m):

Более распространенное название – версия GMRES с рестартами. Хорошо бы в этом разделе пояснить, почему «на практике используется» именно такая версия.


4 Пункт 1.6

--Evgeny Mortikov (обсуждение) 05:42, 2 декабря 2016 (MSK)

Если пренебречь сложностью вычисления [math] y_m [/math], то общую сложность алгоритма GMRES можно разделить на две части:

Нужно пояснить почему сложностью расчета [math] y_m [/math] можно пренебречь.


5 Пункт 1.8

--Evgeny Mortikov (обсуждение) 05:42, 2 декабря 2016 (MSK)

...нахождение взвешенной суммы векторов. Линейная комбинация векторов?

  • Взвешенная сумма векторов - это линейная комбинация векторов


Поэтому при увеличении эффективности использования вычислительных ресурсов и ресурсов памяти вычислительной машины при выполнении этих операций повышается эффективность метода в целом. Достигается это применением при выполнении перечисленных операций аппарата параллельных вычислений.

Этот абзац не понятен и его нужно переформулировать. Например, применение параллельных вычислений не обязательно приводит к эффективности использованию вычислительных ресурсов.

  • этот абзац поправил


При выполнении параллельного алгоритма решения систем линейных алгебраических уравнений необходимо распределить входные данные наиболее рациональным способом. Матрица коэффициентов разбивается на непрерывные горизонтальные полосы. Распределение вектора правой части и начального приближения выполнено по принципу дублирования, т.е. все элементы векторов скопированы на все процессоры.

Почему данный подход является «наиболее рациональным»? Например, n (размер вектора) может быть очень большим и вектор не будет помещаться в память одного процессора.

  • этот подход здесь рассматрвиается как один из возможных - и в зависимости от размера входных данных и от вычислительной машины и процессора можно применять разные методы распределения входных данных


Результатом выполнения рассматриваемых операций является, вектор, части которого расположены на участвовавших в вычислениях процессорах. Для объединения результатов расчета и получения полного вектора на каждом процессоре вычислительной системы необходимо выполнить операцию сбора данных.

Требуются ли сборки данных в таком подходе на каждой итерации метода?

  • Сбор данных потребуется на каждой итерации метода

6 Пункт 1.10

--Evgeny Mortikov (обсуждение) 05:42, 2 декабря 2016 (MSK)

Если используется неперезапускаемый метод, GMRES будет сходиться за не более [math] n [/math] шагов.

Будет просто сходиться с некоторой точностью, или в точной арифметике – это прямой метод за n шагов?

  • Хотя GMRES используется как итерационный метод - теоретически он является прямым: реализуемый в точной арифметике, он приводит к точному решению системы порядка [math]n[/math] не более, чем в [math]n[/math] шагов

Существуют примеры, для которых метод застаивается и сходимость есть только на [math]m[/math]-м шаге. Для таких систем, любой выбор [math] m [/math] меньше, чем [math] n [/math] - не сходится.

Т.е. за n-1 шагов ошибка может быть сколь угодно большой? Нужно привести пример, ссылку или пояснить – в каком случае метод не сходится менее чем за n шагов?

  • ошибка в таком случае будет больше, чем приемлемая и сходимости, соответственно, не будет; примеров на данный случай к сожалению не смог найти


Опечатка - включает в себя чрезмерную работы

  • опечатку поправил

7 Пункт 2.4

--Evgeny Mortikov (обсуждение) 05:42, 2 декабря 2016 (MSK)

Запускалась ли данная реализация GMRES в PETSc самостоятельно на указанном кластере?

C чем связано то, что авторы работы [3] из списка литературы получили практически точно такой же график масштабируемости, но для предобусловленного метода GMRES, с помощью той же библиотеки PETSc и на том же самом кластере?

Соответствует ли разбиение входных данных по параллельным процессам в реализации PETSc тому, что приведено в пункте 1.8? Описание алгоритма и то, что тестируется должно быть согласовано. Входит ли в замер времени счета описанная в пункте 1.8 сборка вектора решения на управляющем процессоре?

Нужно также указать размерность задачи, описать структуру матрицы в экспериментах, условие на окончание итерационного процесса.


  • самостоятельно данная реализация не запускалась. в других статьях по этой теме есть результаты запуска реализации, взятой с GitHub, с использованием библиотеки MPI. так как из всех статей по одной теме далее будет собираться одна большая, содержащая результаты всех статей, то я решил поискать работы по данному методу, в том числе иностранных научных исследователей, где использовались другие библиотеки, в частности PETSc. код, используемый при запуске, так же можно найти на GitHub, как и реализации метода при помощи других библиотек (в статьях других студентов). в указанных в списке используемой литературы статьях (для данной темы нашлись статьи, в которых использовались предобуславливатели, и поэтому здесь указан график для преобусловленного метода) описаны также задачи, на которых можно применять данный метод и структуры матриц, которые соответствуют системам уравнений. точность метода, то есть допустимая ошибка, равна 1E-6. Про время явно в этих статьях не указано, но в других работах (не совсем подходящих для данной статьи), видел указание, что время замерялось полное, то есть с учетом затрат временных ресурсов на сборку векторов, кроме того в библиотеке PETSc можно обращаться к часам явно через команды PetscLogDouble time; и PetscGetTime(&time);CHKERRQ(ierr). насчет размера системы - в статье указано, что решается линейная система, полученная из дискритезации уравнения Гельмгольца (то есть берется трехмерная сетка с определенным шагом и в каждой точке сетки фиксируют значения) - берется суперклетка размером 3х3х3 и периодически повторяется вдоль одной из осей с факторами 1, 2, 3, 8, 16; в суперклетках равномерно от идеальных позиций распределены атомы, для которых как раз решается система уравнений (7a)-(7b), указанная в статье. размер системы здесь - это получается количество атомов в этих суперклетках.



Добрый день. Начал проверять статью и оставил следующие заметки

Здравствуйте. Немного исправил статью, исходя из ваших замечаний.

8 1.2

На мой взгляд, нужны определения span? l2-норма?

Alexander34396 Дано пояснение обозначения span.Вместо l2-норма теперь используется Евклидова норма.

9 1.2.1

Вот я читаю этот раздел как человек со стороны и вижу много формул. Почему они именно такие? В чем суть этого алгоритма?

Alexander34396 Перед алгоритмом добавлено описание идеи алгоритма и пояснения к формулам.

10 1.2.2

Новые определения

Alexander34396 Добавлены некоторые пояснения.Добавлена ссылка на статью - вращения Гивенса.

Затем я остановился, и у меня главные вопрос. Возможно ли сделать статью такой, чтобы для ее прочтения не требовалось обращаться к куче дополнительных источников? Вот я человек со стороны, хотя и заканчивал мехмат. Я могу разобраться со всем написанным здесь, но для этого мне придется гуглить кучу материалов. Но, насколько я понимаю, цель таких статей - быть более полными.

Alexander34396 На мой взгляд, формат статей algo-wiki не подразумевает подробных объяснений и выводов формул, поэтому я добавил только некоторые пояснения, которые делают повествование более последовательным и несколько более понятным. При этом для полного понимания описанного метода для человека со стороны всё равно придётся обращаться к сторонним источникам.

Можете или добавить объяснений или возразить мне. В любом случае, пока с прочтением остановился, жду ответа или исправление (а лучше и того, и другого)


11 2.4

Dan (обсуждение) 19:09, 30 ноября 2016 (MSK) принято