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

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 8 промежуточных версий 4 участников)
Строка 1: Строка 1:
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:42, 2 декабря 2016 (MSK) К вашей работе есть несколько замечаний по содержанию и вопросы по пункту с масштабируемостью. Новая серия замечаний стоит с моей подписью.
 +
 +
 +
 +
----
 +
 +
== Пункт 1.2.3 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:42, 2 декабря 2016 (MSK)
 +
 +
'''вычислить <math> r_m </math> и остановиться,если требуемая точность была достигнута, иначе повторить.'''
 +
 +
Как здесь предлагается оценивать достижение требуемой точности?
 +
 +
 +
== Пункт 1.4 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:42, 2 декабря 2016 (MSK)
 +
 +
'''Умножение вектора на скаляр;'''
 +
 +
'''Деление вектора на скаляр.'''
 +
 +
В чем с вычислительной точки зрения принципиальная разница между умножением и делением вектора на скаляр? Деление всегда можно записать в виде умножение на обратную величину.
 +
 +
 +
== Пункт 1.5 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:42, 2 декабря 2016 (MSK)
 +
 +
'''На практике используется перезапускаемая версия метода - GMRES(m):'''
 +
 +
Более распространенное название – версия GMRES с рестартами. Хорошо бы в этом разделе пояснить, почему «на практике используется» именно такая версия.
 +
 +
 +
== Пункт 1.6 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:42, 2 декабря 2016 (MSK)
 +
 +
'''Если пренебречь сложностью вычисления <math> y_m </math>, то общую сложность алгоритма GMRES можно разделить на две части:'''
 +
 +
Нужно пояснить почему сложностью расчета <math> y_m </math>  можно пренебречь.
 +
 +
 +
== Пункт 1.8 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:42, 2 декабря 2016 (MSK)
 +
 +
'''...нахождение взвешенной суммы векторов.''' Линейная комбинация векторов?
 +
 +
* Взвешенная сумма векторов - это линейная комбинация векторов
 +
 +
 +
'''Поэтому при увеличении эффективности использования вычислительных ресурсов и ресурсов памяти вычислительной машины при выполнении этих операций повышается эффективность метода в целом. Достигается это применением при выполнении перечисленных операций аппарата параллельных вычислений.'''
 +
 +
Этот абзац не понятен и его нужно переформулировать. Например, применение параллельных вычислений не обязательно приводит к эффективности использованию вычислительных ресурсов.
 +
 +
* этот абзац поправил
 +
 +
 +
'''При выполнении параллельного алгоритма решения систем линейных алгебраических уравнений необходимо распределить входные данные наиболее рациональным способом. Матрица коэффициентов разбивается на непрерывные горизонтальные полосы. Распределение вектора правой части и начального приближения выполнено по принципу дублирования, т.е. все элементы векторов скопированы на все процессоры.'''
 +
 +
Почему данный подход является «наиболее рациональным»? Например, n (размер вектора) может быть очень большим и вектор не будет помещаться в память одного процессора.
 +
 +
* этот подход здесь рассматрвиается как один из возможных - и в зависимости от размера входных данных и от вычислительной машины и процессора можно применять разные методы распределения входных данных
 +
 +
 +
'''Результатом выполнения рассматриваемых операций является, вектор, части которого расположены на участвовавших в вычислениях процессорах. Для объединения результатов расчета и получения полного вектора на каждом процессоре вычислительной системы необходимо выполнить операцию сбора данных.'''
 +
 +
Требуются ли сборки данных в таком подходе на каждой итерации метода?
 +
 +
* Сбор данных потребуется на каждой итерации метода
 +
 +
== Пункт 1.10 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника: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 шагов?
 +
 +
* ошибка в таком случае будет больше, чем приемлемая и сходимости, соответственно, не будет; примеров на данный случай к сожалению не смог найти
 +
 +
 +
Опечатка - '''включает в себя чрезмерную работы'''
 +
 +
* опечатку поправил
 +
 +
== Пункт 2.4 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника: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), указанная в статье. размер системы здесь - это получается количество атомов в этих суперклетках.
 +
----
 +
 +
 +
 +
 +
 
Добрый день. Начал проверять статью и оставил следующие заметки
 
Добрый день. Начал проверять статью и оставил следующие заметки
 +
 +
Здравствуйте. Немного исправил статью, исходя из ваших замечаний.
  
 
= 1.2 =  
 
= 1.2 =  
Строка 5: Строка 115:
 
span?
 
span?
 
l2-норма?
 
l2-норма?
 +
 +
: [[Участник:Alexander34396|Alexander34396]] Дано пояснение обозначения span.Вместо l2-норма теперь используется Евклидова норма.
  
 
= 1.2.1 =  
 
= 1.2.1 =  
 
Вот я читаю этот раздел как человек со стороны и вижу много формул. Почему они именно такие? В чем суть этого алгоритма?
 
Вот я читаю этот раздел как человек со стороны и вижу много формул. Почему они именно такие? В чем суть этого алгоритма?
 +
 +
: [[Участник:Alexander34396|Alexander34396]] Перед алгоритмом добавлено описание идеи алгоритма и пояснения к формулам.
  
 
= 1.2.2 =  
 
= 1.2.2 =  
 
Новые определения
 
Новые определения
  
 +
: [[Участник:Alexander34396|Alexander34396]] Добавлены некоторые пояснения.Добавлена ссылка на статью - вращения Гивенса.
  
 
Затем я остановился, и у меня главные вопрос. Возможно ли сделать статью такой, чтобы для ее прочтения не требовалось обращаться к куче дополнительных источников? Вот я человек со стороны, хотя и заканчивал мехмат. Я могу разобраться со всем написанным здесь, но для этого мне придется гуглить кучу материалов. Но, насколько я понимаю, цель таких статей - быть более полными.
 
Затем я остановился, и у меня главные вопрос. Возможно ли сделать статью такой, чтобы для ее прочтения не требовалось обращаться к куче дополнительных источников? Вот я человек со стороны, хотя и заканчивал мехмат. Я могу разобраться со всем написанным здесь, но для этого мне придется гуглить кучу материалов. Но, насколько я понимаю, цель таких статей - быть более полными.
 +
 +
: [[Участник:Alexander34396|Alexander34396]]  На мой взгляд, формат статей algo-wiki не подразумевает подробных объяснений и выводов формул, поэтому я добавил только некоторые пояснения, которые делают повествование более последовательным и несколько более понятным. При этом для полного понимания описанного метода для человека со стороны всё равно придётся обращаться к сторонним источникам.
  
 
Можете или добавить объяснений или возразить мне. В любом случае, пока с прочтением остановился, жду ответа или исправление (а лучше и того, и другого)
 
Можете или добавить объяснений или возразить мне. В любом случае, пока с прочтением остановился, жду ответа или исправление (а лучше и того, и другого)
 +
 +
 +
= 2.4 =
 +
[[Участник:Dan|Dan]] ([[Обсуждение участника:Dan|обсуждение]]) 19:09, 30 ноября 2016 (MSK) '''принято'''

Текущая версия на 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) принято

Источник — https://algowiki-project.org/w/ru/index.php?title=Обсуждение_участника:Alexander34396&oldid=21331