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

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показана 21 промежуточная версия 4 участников)
Строка 1: Строка 1:
--[[Участник:Vvf63|Vvf63]] ([[Обсуждение участника:Vvf63|обсуждение]]) 00:06, 1 ноября 2016 (MSK)== Статья [[Участник:Pandvik/Ортогонализация Грама - Шмидта]] ==
+
== Статья [[Участник:Pandvik/Ортогонализация Грама - Шмидта]] - по существу ==
 +
 
 +
=== Замечания по существу (могут появляться не сразу) ===
 +
 
 +
* В 2.7 Ортогонализация с использованием алгоритма SVD - другой алгоритм, это скорее в свойства (как сравнение для решения задачи), это не реализация. --[[Участник:Frolov|Фролов А.В.]] ([[Обсуждение участника:Frolov|обсуждение]]) 15:36, 7 ноября 2016 (MSK)
 +
* В свойствах отмечено, что модифицированный (с переортогонализацией) более устойчив, но не зафиксирована неустойчивость выбранного алгоритма (неустойчив по ортогональности получаемых векторов) --[[Участник:Frolov|Фролов А.В.]] ([[Обсуждение участника:Frolov|обсуждение]]) 15:46, 7 ноября 2016 (MSK)
 +
* Для алгоритма без переортогонализации выбран неудачный порядок (сначала сумма всех вычитаемых компонент, потом вычитание), хотя напрашивается и боле экономен другой порядок. Соответственно подмывается и описание макроструктуры - база там другая. --[[Участник:Frolov|Фролов А.В.]] ([[Обсуждение участника:Frolov|обсуждение]]) 15:52, 7 ноября 2016 (MSK)
 +
* Литература без положенных для цитирования реквизитов - нехорошо. Ладно, что не классика, это дело вкуса, но годы и издательства необходимо указывать. --[[Участник:Frolov|Фролов А.В.]] ([[Обсуждение участника:Frolov|обсуждение]]) 15:48, 7 ноября 2016 (MSK)
 +
 
 +
=== Исправления и ответы на них ===
 +
 
 +
* Алгоритм с использованием SVD был перенесён в свойства. --[[Участник:Vvf63|Vvf63]] ([[Обсуждение участника:Vvf63|обсуждение]]) 19:53, 13 ноября 2016 (MSK)
 +
 
 +
* Добавлено уточнение о численной неустойчивости алгоритма при ошибках округления. --[[Участник:Vvf63|Vvf63]] ([[Обсуждение участника:Vvf63|обсуждение]]) 19:53, 13 ноября 2016 (MSK)
 +
 
 +
* Была выделена сумма для большей наглядности. Если этого недостаточно, могу продублировать действия для k-того шага на примере шага N. --[[Участник:Vvf63|Vvf63]] ([[Обсуждение участника:Vvf63|обсуждение]]) 19:53, 13 ноября 2016 (MSK)
 +
** Неудачность не в этом, а в том, что при такой группировке теряется дополнительно порядок по распараллеливанию. Кстати, алгоритм с переортогонализацией так просто не распараллелить, а вот именно этот, без переортогонализации, с надлежащим порядком вычитания более параллелен. --[[Участник:Frolov|Фролов А.В.]] ([[Обсуждение участника:Frolov|обсуждение]]) 09:53, 16 ноября 2016 (MSK)
 +
*** Если я правильно понимаю, то Вам не нравится запись вида <math>a-(proj+proj+...)</math>, а нравится <math>a-proj-proj-...)</math>? Или наоборот? С моей точки зрения, запись <math>a-proj-proj-...)</math> выглядит более привлекательной в плане написания программы (Инициализировать вектора b векторами a и потом вычитать проекции). На сколько я понимаю, раньше везде была указана эта форма записи. Однако запись <math>a-(proj+proj+...)</math> выглядит более математической и позволяет сгруппировать все элементы проекций под знаком суммы. Но в целом обе этих формы записи отличаются незначительно. --[[Участник:Pandvik|Pandvik]] ([[Обсуждение участника:Pandvik|обсуждение]]) 23:23, 16 ноября 2016 (MSK)
 +
**** Математика математикой, но алгоритмически последовательность другая. И граф принципиально другой будет, с меньшим критическим путём, тем более если выбрали без переортогонализации - надо при его недостатках (неустойчивость) использовать преимущества. А так их не видно. --[[Участник:Frolov|Фролов А.В.]] ([[Обсуждение участника:Frolov|обсуждение]]) 13:28, 8 декабря 2016 (MSK) 
 +
***** Преимущества алгоритма без переортогонализации собственно рассказываются в разделе про параллелизм алгоритма. Ведь как Вы писали раньше, алгоритм с переортогонализацией так распараллелить не получится. Собственно, как мне кажется, на информационных графах (которые присутствуют в статье) показаны преимущества алгоритма без переортогонализации (а именно - возможность его распараллелить). --[[Участник:Pandvik|Pandvik]] ([[Обсуждение участника:Pandvik|обсуждение]]) 12:14, 14 декабря 2016 (MSK)
 +
***** На счёт различий между <math>a-proj-proj-...)</math> и <math>a-(proj+proj+...)</math> - на сколько я понимаю это почти никак не будет влиять на длину критического пути. Возможно критический путь увеличится на одну операцию векторного сложения. Вам не нравится потери связанные с этим шагом? Я загрузил новую картинку, которая показывает правильный порядок отрицаний. https://algowiki-project.org/algowiki/pool/images/archive/c/c5/20161214090834%21Diagram_Gram-Schmidt_DataFlow_proj.png К сожалению, у меня возникли проблемы с тем, чтобы установить правильную версию картинки на страницу. --[[Участник:Pandvik|Pandvik]] ([[Обсуждение участника:Pandvik|обсуждение]]) 12:14, 14 декабря 2016 (MSK)
 +
****** 1. Оценка влияния неверна. 2. Решайте эти проблемы, и всё с этим вопросом закончено будет. --[[Участник:Frolov|Фролов А.В.]] ([[Обсуждение участника:Frolov|обсуждение]]) 15:29, 14 декабря 2016 (MSK)
 +
******* Картинка всё таки загрузилась нормально, просто с некоторым запозданием. Я понял свою ошибку. Критический путь увеличится на произведение векторов умноженное на число векторов. Это уже получается много. --[[Участник:Pandvik|Pandvik]] ([[Обсуждение участника:Pandvik|обсуждение]]) 23:09, 14 декабря 2016 (MSK)
 +
*** Для пункта 2.4 был реализован алгоритм без переортогонализации. --[[Участник:Pandvik|Pandvik]] ([[Обсуждение участника:Pandvik|обсуждение]]) 23:23, 16 ноября 2016 (MSK)
 +
 
 +
* Были внесены изменения в литературу. В некоторых статьях в качестве издательства используются названия университетов. Нужно ли писать М::<название_университета>? --[[Участник:Vvf63|Vvf63]] ([[Обсуждение участника:Vvf63|обсуждение]]) 19:53, 13 ноября 2016 (MSK)
 +
** Лучше писать. Вообще стандартизация не до конца проведена. В одном Москва без двоеточия, в другом М:. --[[Участник:Frolov|Фролов А.В.]] ([[Обсуждение участника:Frolov|обсуждение]]) 13:30, 8 декабря 2016 (MSK)
 +
*** Подправили литературу.--[[Участник:Vvf63|Vvf63]] ([[Обсуждение участника:Vvf63|обсуждение]]) 23:40, 14 декабря 2016 (MSK)
 +
 
 +
== Статья [[Участник:Pandvik/Ортогонализация Грама - Шмидта]] ==
  
 
=== Отсутствующие части ===
 
=== Отсутствующие части ===
Строка 10: Строка 39:
 
=== DONE ===
 
=== DONE ===
 
* Обновлены картинки (добавлены/исправлены стрелки). Добавлены потерявшиеся стрелки; Изменено направление стрелок для большей наглядности; Входные и выходные данные окрашены в разные цвета, а назначения раскрашенные указано в тексте раздела. --[[Участник:Pandvik|Pandvik]] ([[Обсуждение участника:Pandvik|обсуждение]]) 23:40, 31 октября 2016 (MSK)
 
* Обновлены картинки (добавлены/исправлены стрелки). Добавлены потерявшиеся стрелки; Изменено направление стрелок для большей наглядности; Входные и выходные данные окрашены в разные цвета, а назначения раскрашенные указано в тексте раздела. --[[Участник:Pandvik|Pandvik]] ([[Обсуждение участника:Pandvik|обсуждение]]) 23:40, 31 октября 2016 (MSK)
 +
** Граф нужен не сам по себе, а чтобы наглядно показать структуру алгоритма. Граф на рис.3, по-моему, максимально запутанный, понято по нему что-либо очень сложно. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 18:11, 1 ноября 2016 (MSK)
 +
*** Мне кажется, что для описания основной структуры алгоритма достаточно Рис.1. Этот  рисунок не загромождён лишними данными и позволяет оценить возможности параллелизма для данного алгоритма. Рисунок 3 является попыткой более подробно составить граф зависимости, и приводит к слишком сильному загромождению картинки стрелками зависимостей. Я постарался переделать этот рисунок. Исправил ошибки, переделал и раскрасил стрелки. Возможно, он стал выглядеть немного получше. --[[Участник:Pandvik|Pandvik]] ([[Обсуждение участника:Pandvik|обсуждение]]) 09:47, 3 ноября 2016 (MSK)
 +
 +
*Внесено уточнение в макроструктуру алгоритма (1.4). Было добавлено пояснение к преобладающим операциям алгоритма. --[[Участник:Vvf63|Vvf63]] ([[Обсуждение участника:Vvf63|обсуждение]]) 00:06, 1 ноября 2016 (MSK)
 +
** Преобладающие операции понятны, но структура алгоритма на макроуровне не раскрыта. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 18:11, 1 ноября 2016 (MSK)
 +
*** Добавил описание в 1.4 .--[[Участник:Vvf63|Vvf63]] ([[Обсуждение участника:Vvf63|обсуждение]]) 17:27, 2 ноября 2016 (MSK)
  
*Внесено уточнение в макроструктуру алгоритма (1.4). Было добавлено пояснение к преобладающим операциям алгоритма. --[[Участник:Vvf63|Филимонов Владимир]] --[[Участник:Vvf63|Vvf63]] ([[Обсуждение участника:Vvf63|обсуждение]]) 00:06, 1 ноября 2016 (MSK)
+
*Указан вклад каждого из авторов. --[[Участник:Vvf63|Vvf63]] ([[Обсуждение участника:Vvf63|обсуждение]]) 00:06, 1 ноября 2016 (MSK)
  
*Указан вклад каждого из авторов. --[[Участник:Vvf63|Филимонов Владимир]]--[[Участник:Vvf63|Vvf63]] ([[Обсуждение участника:Vvf63|обсуждение]]) 00:06, 1 ноября 2016 (MSK)
+
* В разделе 2.4 не приведены все параметры запуска теста - какой компилятор, с какими опциями использовался, какие версии библиотек, на каких узлах проводился запуск и т.д. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:58, 16 ноября 2016 (MSK)
 +
** Добавлено описание деталей эксперимента. Добавлены некоторые выводы из результатов эксперимента. --[[Участник:Pandvik|Pandvik]] ([[Обсуждение участника:Pandvik|обсуждение]]) 23:00, 16 ноября 2016 (MSK)

Текущая версия на 23:40, 14 декабря 2016

1 Статья Участник:Pandvik/Ортогонализация Грама - Шмидта - по существу

1.1 Замечания по существу (могут появляться не сразу)

  • В 2.7 Ортогонализация с использованием алгоритма SVD - другой алгоритм, это скорее в свойства (как сравнение для решения задачи), это не реализация. --Фролов А.В. (обсуждение) 15:36, 7 ноября 2016 (MSK)
  • В свойствах отмечено, что модифицированный (с переортогонализацией) более устойчив, но не зафиксирована неустойчивость выбранного алгоритма (неустойчив по ортогональности получаемых векторов) --Фролов А.В. (обсуждение) 15:46, 7 ноября 2016 (MSK)
  • Для алгоритма без переортогонализации выбран неудачный порядок (сначала сумма всех вычитаемых компонент, потом вычитание), хотя напрашивается и боле экономен другой порядок. Соответственно подмывается и описание макроструктуры - база там другая. --Фролов А.В. (обсуждение) 15:52, 7 ноября 2016 (MSK)
  • Литература без положенных для цитирования реквизитов - нехорошо. Ладно, что не классика, это дело вкуса, но годы и издательства необходимо указывать. --Фролов А.В. (обсуждение) 15:48, 7 ноября 2016 (MSK)

1.2 Исправления и ответы на них

  • Алгоритм с использованием SVD был перенесён в свойства. --Vvf63 (обсуждение) 19:53, 13 ноября 2016 (MSK)
  • Добавлено уточнение о численной неустойчивости алгоритма при ошибках округления. --Vvf63 (обсуждение) 19:53, 13 ноября 2016 (MSK)
  • Была выделена сумма для большей наглядности. Если этого недостаточно, могу продублировать действия для k-того шага на примере шага N. --Vvf63 (обсуждение) 19:53, 13 ноября 2016 (MSK)
    • Неудачность не в этом, а в том, что при такой группировке теряется дополнительно порядок по распараллеливанию. Кстати, алгоритм с переортогонализацией так просто не распараллелить, а вот именно этот, без переортогонализации, с надлежащим порядком вычитания более параллелен. --Фролов А.В. (обсуждение) 09:53, 16 ноября 2016 (MSK)
      • Если я правильно понимаю, то Вам не нравится запись вида [math]a-(proj+proj+...)[/math], а нравится [math]a-proj-proj-...)[/math]? Или наоборот? С моей точки зрения, запись [math]a-proj-proj-...)[/math] выглядит более привлекательной в плане написания программы (Инициализировать вектора b векторами a и потом вычитать проекции). На сколько я понимаю, раньше везде была указана эта форма записи. Однако запись [math]a-(proj+proj+...)[/math] выглядит более математической и позволяет сгруппировать все элементы проекций под знаком суммы. Но в целом обе этих формы записи отличаются незначительно. --Pandvik (обсуждение) 23:23, 16 ноября 2016 (MSK)
        • Математика математикой, но алгоритмически последовательность другая. И граф принципиально другой будет, с меньшим критическим путём, тем более если выбрали без переортогонализации - надо при его недостатках (неустойчивость) использовать преимущества. А так их не видно. --Фролов А.В. (обсуждение) 13:28, 8 декабря 2016 (MSK)
          • Преимущества алгоритма без переортогонализации собственно рассказываются в разделе про параллелизм алгоритма. Ведь как Вы писали раньше, алгоритм с переортогонализацией так распараллелить не получится. Собственно, как мне кажется, на информационных графах (которые присутствуют в статье) показаны преимущества алгоритма без переортогонализации (а именно - возможность его распараллелить). --Pandvik (обсуждение) 12:14, 14 декабря 2016 (MSK)
          • На счёт различий между [math]a-proj-proj-...)[/math] и [math]a-(proj+proj+...)[/math] - на сколько я понимаю это почти никак не будет влиять на длину критического пути. Возможно критический путь увеличится на одну операцию векторного сложения. Вам не нравится потери связанные с этим шагом? Я загрузил новую картинку, которая показывает правильный порядок отрицаний. https://algowiki-project.org/algowiki/pool/images/archive/c/c5/20161214090834%21Diagram_Gram-Schmidt_DataFlow_proj.png К сожалению, у меня возникли проблемы с тем, чтобы установить правильную версию картинки на страницу. --Pandvik (обсуждение) 12:14, 14 декабря 2016 (MSK)
            • 1. Оценка влияния неверна. 2. Решайте эти проблемы, и всё с этим вопросом закончено будет. --Фролов А.В. (обсуждение) 15:29, 14 декабря 2016 (MSK)
              • Картинка всё таки загрузилась нормально, просто с некоторым запозданием. Я понял свою ошибку. Критический путь увеличится на произведение векторов умноженное на число векторов. Это уже получается много. --Pandvik (обсуждение) 23:09, 14 декабря 2016 (MSK)
      • Для пункта 2.4 был реализован алгоритм без переортогонализации. --Pandvik (обсуждение) 23:23, 16 ноября 2016 (MSK)
  • Были внесены изменения в литературу. В некоторых статьях в качестве издательства используются названия университетов. Нужно ли писать М::<название_университета>? --Vvf63 (обсуждение) 19:53, 13 ноября 2016 (MSK)
    • Лучше писать. Вообще стандартизация не до конца проведена. В одном Москва без двоеточия, в другом М:. --Фролов А.В. (обсуждение) 13:30, 8 декабря 2016 (MSK)

2 Статья Участник:Pandvik/Ортогонализация Грама - Шмидта

2.1 Отсутствующие части

2.2 Замечания по тексту

  • В разделе 1.4 требуется привести описание алгоритма на верхнем уровне (на основе макроопераций). Александр Сергеевич Антонов (обсуждение) 17:27, 31 октября 2016 (MSK)
  • Структура графов на рис.1-3 непонятна. Если двойными кругами показаны элементы данных, то лучше их разделить на входные и выходные. Не всё понятно и с дугами, например, на рис.3 оранжевым овалом обозначаются скалярные произведения двух векторов, но в некоторые из овалов входит только одна дуга, а откуда берётся второй аргумент? Александр Сергеевич Антонов (обсуждение) 17:27, 31 октября 2016 (MSK)

2.3 DONE

  • Обновлены картинки (добавлены/исправлены стрелки). Добавлены потерявшиеся стрелки; Изменено направление стрелок для большей наглядности; Входные и выходные данные окрашены в разные цвета, а назначения раскрашенные указано в тексте раздела. --Pandvik (обсуждение) 23:40, 31 октября 2016 (MSK)
    • Граф нужен не сам по себе, а чтобы наглядно показать структуру алгоритма. Граф на рис.3, по-моему, максимально запутанный, понято по нему что-либо очень сложно. Александр Сергеевич Антонов (обсуждение) 18:11, 1 ноября 2016 (MSK)
      • Мне кажется, что для описания основной структуры алгоритма достаточно Рис.1. Этот рисунок не загромождён лишними данными и позволяет оценить возможности параллелизма для данного алгоритма. Рисунок 3 является попыткой более подробно составить граф зависимости, и приводит к слишком сильному загромождению картинки стрелками зависимостей. Я постарался переделать этот рисунок. Исправил ошибки, переделал и раскрасил стрелки. Возможно, он стал выглядеть немного получше. --Pandvik (обсуждение) 09:47, 3 ноября 2016 (MSK)
  • Внесено уточнение в макроструктуру алгоритма (1.4). Было добавлено пояснение к преобладающим операциям алгоритма. --Vvf63 (обсуждение) 00:06, 1 ноября 2016 (MSK)
  • В разделе 2.4 не приведены все параметры запуска теста - какой компилятор, с какими опциями использовался, какие версии библиотек, на каких узлах проводился запуск и т.д. Александр Сергеевич Антонов (обсуждение) 15:58, 16 ноября 2016 (MSK)
    • Добавлено описание деталей эксперимента. Добавлены некоторые выводы из результатов эксперимента. --Pandvik (обсуждение) 23:00, 16 ноября 2016 (MSK)