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

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 10 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
Добрый день. Подключаюсь к проверке. Статья мне в целом понравилась, и тем больше от этого хочется добавить замечаний, чтобы довести ее до того вида, чтобы она могла остаться на Алговики.
 
Добрый день. Подключаюсь к проверке. Статья мне в целом понравилась, и тем больше от этого хочется добавить замечаний, чтобы довести ее до того вида, чтобы она могла остаться на Алговики.
 +
 +
'''Уважаемые авторы, к Вашей работе есть новые замечания - они для удобства отделены горизонтальной линией от прошлых.'''
 +
 +
  
 
= Пункт 1.1 =  
 
= Пункт 1.1 =  
Строка 8: Строка 12:
 
'''Однако многие схемы хранения допускают определенную долю нулей, и алгоритм обрабатывает их, как если бы они не были нулями.'''
 
'''Однако многие схемы хранения допускают определенную долю нулей, и алгоритм обрабатывает их, как если бы они не были нулями.'''
 
Тоже непонятно
 
Тоже непонятно
 +
 +
__
 +
 +
Поправили
 +
 +
 +
----
 +
 +
 +
'''Разреженная матрица — матрица с большим количеством нулевых элементов.'''
 +
 +
Все же матрица с большим количеством нулей может быть сильно плотной и так лучше не писать.
 +
 +
 +
'''* есть <math>O(n)</math>. Приве­денное определение полезно только для теоретических целей типа попытки оценить асимптотическое поведение алгоритма.'''
 +
 +
'''* ограничено в строке, в типичном случае от 2 до 10.'''
 +
 +
'''* выражается как <math>n^{1+\gamma}</math>, где <math>\gamma < 1</math>.'''
 +
 +
- Если первое определение подходит только для “теоретического анализа”, то чем лучше третье?
 +
 +
- Второе определение, по-моему, не совсем корректно – оно слишком строгое, не понятно, что за типичный случай, почему именно используется привязка к строкам матрицы, почему именно 2 и 10 (а, например, 1?) и т.д. Есть ли какие-то ссылки на литературу, где такое определение использовалось для анализа или для практических задач? Нужно пояснить смысл такого определения.
 +
 +
 +
'''Всякую разреженную матрицу можно обрабатывать так, как если бы она была плотной: напротив, вся­кую плотную, или заполненную, матрицу можно обрабатывать алгоритмами для разреженных матриц.'''
 +
 +
Как можно обрабатывать плотную матрицу алгоритмами для разреженных матриц, если ее нужно представить в специальном виде?
 +
 +
 +
'''* сохранять разреженность. Хоро­ший алгоритм для разреженных матриц пытается сохранить раз­реженность, по возможности уменьшая заполнение.'''
 +
 +
Это свойство нужно пояснить. Не во всех задачах можно или желательно уменьшать заполнение.
 +
 +
 +
'''В целях упрощения операций с разреженными матрицами многие алгоритмы разрешают также хранить небольшое количество нулевых элементов и оперировать с ними как с ненулевыми.'''
 +
 +
Почему именно небольшое количество нулевых элементов?
 +
 +
  
 
= Пункт 1.1.1.1 =  
 
= Пункт 1.1.1.1 =  
 
Поставьте определение ленточной матрицы в начало. Потому что, начиная читать первую фразу, сначала задаешься вопросом, что это такое
 
Поставьте определение ленточной матрицы в начало. Потому что, начиная читать первую фразу, сначала задаешься вопросом, что это такое
 +
 +
__
 +
 +
Поправили
 +
 +
  
 
= Пункт 1.1.1.2 =  
 
= Пункт 1.1.1.2 =  
 
'''Кроме того, схема является статической, потому что включение нового элемента, лежащего вне оболочки, требует изменения всей структуры (если только не используются записи переменной длины).'''
 
'''Кроме того, схема является статической, потому что включение нового элемента, лежащего вне оболочки, требует изменения всей структуры (если только не используются записи переменной длины).'''
 
Также нужны пояснения
 
Также нужны пояснения
 +
 +
__
 +
 +
Поправили
 +
 +
 +
----
 +
 +
Можно ли описанную схему использовать для хранения несимметричной ленточной матрицы? И общих (необязательно ленточных) симметричных матриц?
 +
 +
 +
= Пункт 1.1.1.5 =
 +
 +
----
 +
 +
'''Такие неупорядоченные представления могут быть весьма удобны в практических вычислениях. Результаты большинства матричных операций получаются неупорядоченными, а их упорядочение стоило бы значительных затрат машинного времени. В то же время, за немногими исключениями, алгоритмы для разреженных матриц не требуют, чтобы их представления были упорядоченными.'''
 +
 +
Хорошо бы привести несколько примеров операций, для которых неупорядоченные представления дают выигрыш.
 +
 +
 +
'''Данный формат используется для симметричных и верхних треугольных матриц, у которых большинство диагональных элементов отличны от нуля.'''
 +
 +
В чем здесь причина требования «большинство диагональных элементов отличны от нуля»? Формат предназначен для только симметричных или только верхних треугольных? Или и для тех и других?
 +
 +
 +
= Пункт 1.1.1.6 =
 +
 +
----
 +
 +
'''Идея разбиения большой матрицы на подматрицы или блоки возникает естественным образом. С блоками можно обращаться, как если бы они были элементами матрицы, и блочная матрица превращается в матрицу из матриц.'''
 +
 +
Это не так, поскольку матричные произведения необязательно коммутативны.
 +
 +
 +
'''Разбиение на блоки играет важную роль в технологии разреженных матриц, потому что многие алгоритмы, сконструированные первоначально для числовых матриц, можно обобщить на случай матриц из матриц. Большая гибкость, связанная с понятием разбиения, может давать определенные  вычислительные преимущества.'''
 +
 +
Хорошо бы пояснить какие вычислительные преимущества это дает.
 +
 +
 +
'''С другой стороны, разбиение можно рассматривать просто как инструмент управления данными, помогающий организовать обмен информацией между оперативной памятью и внешними запоминающими устройствами. '''
 +
 +
Нужно подробнее пояснить какие преимущества блочное разбиение дает при организации обменов информации между оперативной памятью и внешними запоминающими устройствами.
 +
 +
 +
'''Рассмотрим ''неявную схему хранения'', предназначенную главным образом для симметричных матриц с квадратными диагональными блоками.'''
 +
 +
В чем заключается неявность в такой схеме хранения?
 +
  
 
= Пункт 1.1.2 =  
 
= Пункт 1.1.2 =  
 
'''Достоинство этих процедур, с вычислительной точки зрения, состоит в том, что единственная требуемая матрич­ная операция — это повторное умножение матрицы на последо­вательность заполненных векторов; сама матрица не меняется.'''
 
'''Достоинство этих процедур, с вычислительной точки зрения, состоит в том, что единственная требуемая матрич­ная операция — это повторное умножение матрицы на последо­вательность заполненных векторов; сама матрица не меняется.'''
 
Опять непонятно
 
Опять непонятно
 +
 +
__
 +
 +
Не совсем понятно, что именно непонятно. Добавили комментарий
 +
 +
 +
----
 +
 +
'''Умножение разреженной матрицы на вектор используется при вычислении векторов Ланцоша, необходимом при итерационном решении линейных уравнений методом сопряженных градиентов, а также при вычислении собственных значений и собственных векторов матрицы.'''
 +
 +
Умножение разреженной матрицы на вектор используется и во многих других алгоритмах, методах и задачах, чем примечательны именно эти?
 +
 +
 +
'''Достоинство этих процедур, с вычислительной точки зрения, состоит в том, что единственная требуемая матрич­ная операция — это повторное умножение матрицы на последо­вательность заполненных векторов; сама матрица не меняется.'''
 +
 +
Достоинство этих процедур, по сравнению с какими? В некоторых итерационных методах, например, требуется также умножение и транспонированной матрицы на вектор.
 +
 +
 +
'''Следовательно, наиболее релевантными для этих задач являются статические схемы хранения.'''
 +
 +
Есть ли такие схемы хранения, которые при выполнении матрично-векторного произведения изменяют матрицу или требуют изменения структуры данных?
 +
  
 
= Пункт 1.3 =  
 
= Пункт 1.3 =  
 
Почему вычислительное ядро только последовательной версии?
 
Почему вычислительное ядро только последовательной версии?
 
Вычислительное ядро (computational kernel) алгоритма - это часть алгоритма, на которую приходится основное время его работы.
 
Вычислительное ядро (computational kernel) алгоритма - это часть алгоритма, на которую приходится основное время его работы.
 +
 +
__
 +
 +
Поправили
  
 
= Пункт 1.4 =  
 
= Пункт 1.4 =  
 
Наверное, вопрос в том, что алгоритм делает помимо запуска вычислительных ядер?
 
Наверное, вопрос в том, что алгоритм делает помимо запуска вычислительных ядер?
 +
 +
__
 +
 +
Присвоение элементам заполненного вектора-столбца <math>c</math> результатов запуска вычислительных ядер.
  
 
= Пункт 1.5 =  
 
= Пункт 1.5 =  
 
Как была выбрана форма хранения матрицы? Это нужно прокомментировать
 
Как была выбрана форма хранения матрицы? Это нужно прокомментировать
 +
 +
__
 +
 +
Комментарий был ранее, в пункте 1.1.2. Продублировали
 +
 +
 +
 +
= Пункт 1.6 =
 +
 +
----
 +
 +
'''Для алгоритма умножения разреженной матрицы размером <math>n \times m</math>, представленной в формате RR (C) U, на вектор длины <math>m</math> в последовательном (наиболее быстром) варианте требуется:'''
 +
 +
'''* <math>nz</math> сложений (вычитаний),'''
 +
'''* <math>nz</math> умножений,'''
 +
 +
Что здесь понимается как «наиболее быстрый вариант»? Есть ли какие-то более медленные альтернативы? Оценка <math>nz</math> сложений похоже не совсем правильная. Например, сколько нужно сложений для матрицы с одним ненулевым элементом в алгоритме 1.5?
 +
 +
 +
'''При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, что ещё больше увеличивает долю умножений и сложений/вычитаний во времени, требуемом для выполнения умножения разреженной матрицы на вектор.'''
 +
 +
Непонятное предложение. Увеличивается и доля сложений и доля умножений? Что меняется, с точки зрения числа операций, если делать расчет с двойной точностью?
 +
 +
  
 
= Пункт 1.7 =  
 
= Пункт 1.7 =  
Строка 37: Строка 189:
  
 
Нам показалось верным отобразить на рисунке именно параллельную версию, на которой будет видно как и произведение одной строки на вектор, так и вычисление всех элементов. Как следует из определения [[глоссарий#Граф алгоритма|графа алгоритма]], он должен давать удобное представление не только ядра, но и позволять рассмотреть алгоритм с параллельной точки зрения.  Внесли небольшое пояснение для рисунка.
 
Нам показалось верным отобразить на рисунке именно параллельную версию, на которой будет видно как и произведение одной строки на вектор, так и вычисление всех элементов. Как следует из определения [[глоссарий#Граф алгоритма|графа алгоритма]], он должен давать удобное представление не только ядра, но и позволять рассмотреть алгоритм с параллельной точки зрения.  Внесли небольшое пояснение для рисунка.
 +
 +
 +
= Пункт 1.8 =
 +
 +
----
 +
 +
'''При классификации по высоте ЯПФ, таким образом, алгоритм умножения разреженной матрицы на вектор относится к алгоритмам ''с линейной сложностью''. При классификации по высоте ЯПФ его сложность также будет ''линейной''.'''
 +
 +
Два раза повторяется сложность при классификации по высоте ЯПФ
 +
 +
  
 
= Пункт 2.4 =  
 
= Пункт 2.4 =  
Строка 44: Строка 207:
  
 
Поправили
 
Поправили
 +
 +
 +
----
 +
 +
Помимо ненулевых элементов нужно указать размерность матрицы и описать матрицу (случайная или нет, если нет, то какая), которая использовалась в экспериментах.
 +
 +
 +
'''Это объясняется быстрым ростом накладных расходов на организацию параллельного выполнения. Это подтверждает предположение о том, что накладные расходы начинают сильно превалировать над вычислениями.'''
 +
 +
Хорошо бы поподробнее описать с чем связаны накладные расходы – обращением к файловой системе или межпроцессорными коммуникациями и какого вида.

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

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

Уважаемые авторы, к Вашей работе есть новые замечания - они для удобства отделены горизонтальной линией от прошлых.


1 Пункт 1.1

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

Что означает фраза, выделенная жирным? Или как-то переформулируйте утверждение, оно не понятно

Однако многие схемы хранения допускают определенную долю нулей, и алгоритм обрабатывает их, как если бы они не были нулями. Тоже непонятно

__

Поправили



Разреженная матрица — матрица с большим количеством нулевых элементов.

Все же матрица с большим количеством нулей может быть сильно плотной и так лучше не писать.


* есть [math]O(n)[/math]. Приве­денное определение полезно только для теоретических целей типа попытки оценить асимптотическое поведение алгоритма.

* ограничено в строке, в типичном случае от 2 до 10.

* выражается как [math]n^{1+\gamma}[/math], где [math]\gamma \lt 1[/math].

- Если первое определение подходит только для “теоретического анализа”, то чем лучше третье?

- Второе определение, по-моему, не совсем корректно – оно слишком строгое, не понятно, что за типичный случай, почему именно используется привязка к строкам матрицы, почему именно 2 и 10 (а, например, 1?) и т.д. Есть ли какие-то ссылки на литературу, где такое определение использовалось для анализа или для практических задач? Нужно пояснить смысл такого определения.


Всякую разреженную матрицу можно обрабатывать так, как если бы она была плотной: напротив, вся­кую плотную, или заполненную, матрицу можно обрабатывать алгоритмами для разреженных матриц.

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


* сохранять разреженность. Хоро­ший алгоритм для разреженных матриц пытается сохранить раз­реженность, по возможности уменьшая заполнение.

Это свойство нужно пояснить. Не во всех задачах можно или желательно уменьшать заполнение.


В целях упрощения операций с разреженными матрицами многие алгоритмы разрешают также хранить небольшое количество нулевых элементов и оперировать с ними как с ненулевыми.

Почему именно небольшое количество нулевых элементов?


2 Пункт 1.1.1.1

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

__

Поправили


3 Пункт 1.1.1.2

Кроме того, схема является статической, потому что включение нового элемента, лежащего вне оболочки, требует изменения всей структуры (если только не используются записи переменной длины). Также нужны пояснения

__

Поправили


Можно ли описанную схему использовать для хранения несимметричной ленточной матрицы? И общих (необязательно ленточных) симметричных матриц?


4 Пункт 1.1.1.5

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

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


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

В чем здесь причина требования «большинство диагональных элементов отличны от нуля»? Формат предназначен для только симметричных или только верхних треугольных? Или и для тех и других?


5 Пункт 1.1.1.6

Идея разбиения большой матрицы на подматрицы или блоки возникает естественным образом. С блоками можно обращаться, как если бы они были элементами матрицы, и блочная матрица превращается в матрицу из матриц.

Это не так, поскольку матричные произведения необязательно коммутативны.


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

Хорошо бы пояснить какие вычислительные преимущества это дает.


С другой стороны, разбиение можно рассматривать просто как инструмент управления данными, помогающий организовать обмен информацией между оперативной памятью и внешними запоминающими устройствами.

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


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

В чем заключается неявность в такой схеме хранения?


6 Пункт 1.1.2

Достоинство этих процедур, с вычислительной точки зрения, состоит в том, что единственная требуемая матрич­ная операция — это повторное умножение матрицы на последо­вательность заполненных векторов; сама матрица не меняется. Опять непонятно

__

Не совсем понятно, что именно непонятно. Добавили комментарий


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

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


Достоинство этих процедур, с вычислительной точки зрения, состоит в том, что единственная требуемая матрич­ная операция — это повторное умножение матрицы на последо­вательность заполненных векторов; сама матрица не меняется.

Достоинство этих процедур, по сравнению с какими? В некоторых итерационных методах, например, требуется также умножение и транспонированной матрицы на вектор.


Следовательно, наиболее релевантными для этих задач являются статические схемы хранения.

Есть ли такие схемы хранения, которые при выполнении матрично-векторного произведения изменяют матрицу или требуют изменения структуры данных?


7 Пункт 1.3

Почему вычислительное ядро только последовательной версии? Вычислительное ядро (computational kernel) алгоритма - это часть алгоритма, на которую приходится основное время его работы.

__

Поправили

8 Пункт 1.4

Наверное, вопрос в том, что алгоритм делает помимо запуска вычислительных ядер?

__

Присвоение элементам заполненного вектора-столбца [math]c[/math] результатов запуска вычислительных ядер.

9 Пункт 1.5

Как была выбрана форма хранения матрицы? Это нужно прокомментировать

__

Комментарий был ранее, в пункте 1.1.2. Продублировали


10 Пункт 1.6

Для алгоритма умножения разреженной матрицы размером [math]n \times m[/math], представленной в формате RR (C) U, на вектор длины [math]m[/math] в последовательном (наиболее быстром) варианте требуется:

* [math]nz[/math] сложений (вычитаний), * [math]nz[/math] умножений,

Что здесь понимается как «наиболее быстрый вариант»? Есть ли какие-то более медленные альтернативы? Оценка [math]nz[/math] сложений похоже не совсем правильная. Например, сколько нужно сложений для матрицы с одним ненулевым элементом в алгоритме 1.5?


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

Непонятное предложение. Увеличивается и доля сложений и доля умножений? Что меняется, с точки зрения числа операций, если делать расчет с двойной точностью?


11 Пункт 1.7

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

__

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


12 Пункт 1.8

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

Два раза повторяется сложность при классификации по высоте ЯПФ


13 Пункт 2.4

Пока пустой?

__

Поправили


Помимо ненулевых элементов нужно указать размерность матрицы и описать матрицу (случайная или нет, если нет, то какая), которая использовалась в экспериментах.


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

Хорошо бы поподробнее описать с чем связаны накладные расходы – обращением к файловой системе или межпроцессорными коммуникациями и какого вида.

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