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

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
 
Добрый день. Подключаюсь к проверке. Статья мне в целом понравилась, и тем больше от этого хочется добавить замечаний, чтобы довести ее до того вида, чтобы она могла остаться на Алговики.
 
Добрый день. Подключаюсь к проверке. Статья мне в целом понравилась, и тем больше от этого хочется добавить замечаний, чтобы довести ее до того вида, чтобы она могла остаться на Алговики.
 +
 +
'''Уважаемые авторы, к Вашей работе есть новые замечания - они для удобства отделены горизонтальной линией от прошлых.'''
 +
 +
  
 
= Пункт 1.1 =  
 
= Пункт 1.1 =  
Строка 12: Строка 16:
  
 
Поправили
 
Поправили
 +
 +
 +
----
 +
 +
 +
'''Разреженная матрица — матрица с большим количеством нулевых элементов.'''
 +
 +
Все же матрица с большим количеством нулей может быть сильно плотной и так лучше не писать.
 +
 +
 +
'''* есть <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 =  
Строка 19: Строка 59:
  
 
Поправили
 
Поправили
 +
 +
  
 
= Пункт 1.1.1.2 =  
 
= Пункт 1.1.1.2 =  
Строка 27: Строка 69:
  
 
Поправили
 
Поправили
 +
 +
 +
----
 +
 +
Можно ли описанную схему использовать для хранения несимметричной ленточной матрицы? И общих (необязательно ленточных) симметричных матриц?
 +
 +
 +
= Пункт 1.1.1.5 =
 +
 +
----
 +
 +
'''Такие неупорядоченные представления могут быть весьма удобны в практических вычислениях. Результаты большинства матричных операций получаются неупорядоченными, а их упорядочение стоило бы значительных затрат машинного времени. В то же время, за немногими исключениями, алгоритмы для разреженных матриц не требуют, чтобы их представления были упорядоченными.'''
 +
 +
Хорошо бы привести несколько примеров операций, для которых неупорядоченные представления дают выигрыш.
 +
 +
 +
'''Данный формат используется для симметричных и верхних треугольных матриц, у которых большинство диагональных элементов отличны от нуля.'''
 +
 +
В чем здесь причина требования «большинство диагональных элементов отличны от нуля»? Формат предназначен для только симметричных или только верхних треугольных? Или и для тех и других?
 +
 +
 +
= Пункт 1.1.1.6 =
 +
 +
----
 +
 +
'''Идея разбиения большой матрицы на подматрицы или блоки возникает естественным образом. С блоками можно обращаться, как если бы они были элементами матрицы, и блочная матрица превращается в матрицу из матриц.'''
 +
 +
Это не так, поскольку матричные произведения необязательно коммутативны.
 +
 +
 +
'''Разбиение на блоки играет важную роль в технологии разреженных матриц, потому что многие алгоритмы, сконструированные первоначально для числовых матриц, можно обобщить на случай матриц из матриц. Большая гибкость, связанная с понятием разбиения, может давать определенные  вычислительные преимущества.'''
 +
 +
Хорошо бы пояснить какие вычислительные преимущества это дает.
 +
 +
 +
'''С другой стороны, разбиение можно рассматривать просто как инструмент управления данными, помогающий организовать обмен информацией между оперативной памятью и внешними запоминающими устройствами. '''
 +
 +
Нужно подробнее пояснить какие преимущества блочное разбиение дает при организации обменов информации между оперативной памятью и внешними запоминающими устройствами.
 +
 +
 +
'''Рассмотрим ''неявную схему хранения'', предназначенную главным образом для симметричных матриц с квадратными диагональными блоками.'''
 +
 +
В чем заключается неявность в такой схеме хранения?
 +
  
 
= Пункт 1.1.2 =  
 
= Пункт 1.1.2 =  
Строка 35: Строка 121:
  
 
Не совсем понятно, что именно непонятно. Добавили комментарий
 
Не совсем понятно, что именно непонятно. Добавили комментарий
 +
 +
 +
----
 +
 +
'''Умножение разреженной матрицы на вектор используется при вычислении векторов Ланцоша, необходимом при итерационном решении линейных уравнений методом сопряженных градиентов, а также при вычислении собственных значений и собственных векторов матрицы.'''
 +
 +
Умножение разреженной матрицы на вектор используется и во многих других алгоритмах, методах и задачах, чем примечательны именно эти?
 +
 +
 +
'''Достоинство этих процедур, с вычислительной точки зрения, состоит в том, что единственная требуемая матрич­ная операция — это повторное умножение матрицы на последо­вательность заполненных векторов; сама матрица не меняется.'''
 +
 +
Достоинство этих процедур, по сравнению с какими? В некоторых итерационных методах, например, требуется также умножение и транспонированной матрицы на вектор.
 +
 +
 +
'''Следовательно, наиболее релевантными для этих задач являются статические схемы хранения.'''
 +
 +
Есть ли такие схемы хранения, которые при выполнении матрично-векторного произведения изменяют матрицу или требуют изменения структуры данных?
 +
  
 
= Пункт 1.3 =  
 
= Пункт 1.3 =  
Строка 57: Строка 161:
  
 
Комментарий был ранее, в пункте 1.1.2. Продублировали
 
Комментарий был ранее, в пункте 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 =  
Строка 65: Строка 189:
  
 
Нам показалось верным отобразить на рисунке именно параллельную версию, на которой будет видно как и произведение одной строки на вектор, так и вычисление всех элементов. Как следует из определения [[глоссарий#Граф алгоритма|графа алгоритма]], он должен давать удобное представление не только ядра, но и позволять рассмотреть алгоритм с параллельной точки зрения.  Внесли небольшое пояснение для рисунка.
 
Нам показалось верным отобразить на рисунке именно параллельную версию, на которой будет видно как и произведение одной строки на вектор, так и вычисление всех элементов. Как следует из определения [[глоссарий#Граф алгоритма|графа алгоритма]], он должен давать удобное представление не только ядра, но и позволять рассмотреть алгоритм с параллельной точки зрения.  Внесли небольшое пояснение для рисунка.
 +
 +
 +
= Пункт 1.8 =
 +
 +
----
 +
 +
'''При классификации по высоте ЯПФ, таким образом, алгоритм умножения разреженной матрицы на вектор относится к алгоритмам ''с линейной сложностью''. При классификации по высоте ЯПФ его сложность также будет ''линейной''.'''
 +
 +
Два раза повторяется сложность при классификации по высоте ЯПФ
 +
 +
  
 
= Пункт 2.4 =  
 
= Пункт 2.4 =  
Строка 72: Строка 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