Обсуждение участника:Blizn

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

Пункт 1.1

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

- есть [math]\displaystyle{ O(n) }[/math]. Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;

- в каждой строке не превышает 10 в типичном случае;

- ограничено [math]\displaystyle{ n^{1+\gamma} }[/math], где [math]\displaystyle{ \gamma \lt 1 }[/math].

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

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

В качестве теоретической основы использовался Писсанецки, ссылка на него указана выше в статье. Текст использовался именно оттуда, ничего своего я не придумывала. Почему именно 10? Потому что, как было сказано, НЕЛЬЗЯ дать строгого определения тому, начиная с какого количества элементов матрица перестаёт быть плотной и начинает считаться разреженной. А значит, что нельзя сказать, что запрещено определить матрицу именно так. По этой же причине ни одно определение не хуже и не лучше, они просто даны разными людьми в попытках дать более строгое определение, чем просто "много нулей".

Пункт 1.1.1.1

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

В данном формате вместо одного двумерного массива, используются три одномерных.

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

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

Пункт 1.1.1.2

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

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

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

Пункт 1.1.2

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

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

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

Это просто примеры, и рассмотрение их значимости и примечательности не относится к теме разреженных матриц.

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

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

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

Пункт 1.6

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

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

[math]\displaystyle{ l }[/math] сложений,

[math]\displaystyle{ l }[/math] умножений.

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

Медленные альтернативы есть везде. Ту же сортировку можно делать обезьянью, а можно сортировать qsort'ом.

Пункт 1.8

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

Можно ли записать параллельный алгоритм, использующий больше чем n процессоров, где n - число строк(столбцов)?

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

Пункт 1.10

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

Таким образом хранение в формате RR(C) не является эффективным для матриц, в которых [math]\displaystyle{ l \gt \frac{xnm - y(n+1)}{x+y} }[/math].

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

Пункт 2.4

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

Нужно явно написать в тексте, что рассматривался целочисленный алгоритм. Почему не вещественное матрично-векторное умножение? Приводимые оценки для числа операций алгоритма (п.1.6, 1.8) разве учитывают вспомогательные целочисленные операции, например, для организации циклов?

Конечно нет, потому что всё это - особенности реализации, зависящие от неё (там же не учитывается время на пересылки, время на вывод данных, на их считывание и так далее). Описание алгоритма не зависит от реализации. Если речь идёт в вычисление "старта" и количестве элементов в строке - это аналог вычисление IAA и IAB, на которые слишком малочисленны, а в пункте 1.6 указано, что "Умножения и сложения составляют основную часть алгоритма."

Целочисленное - потому что захотелось и лично мне так было удобнее при ручном тестировании правильности работы кода. Везде, где идёт определение элементов матрицы и вектора, можно заменить int на double, я считаю, этот вопрос не является принципиальным.

размер матрицы [1000 : 10000] с шагом 1000.

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

Здесь размер матрицы - это её размерность. Матрицы генерировались случайно, а данные стёрты и восстановить их невозможно, а значит я не могу указать точно, сколько именно было ненулевых элементов. Впрочем, из генератора видно, что число нулевых и ненулевых элементов было где-то 50/50.

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

Что значит "структура матрицы"? Матрица, как я и писала, генерировалась случайно с помощью функций языка Python. Что же касается чтения в самом начале указано, что каждый процессор считает кусок данных, предоставленных ему. Происходит это 1 раз и в самом начале.

Статья Участник:Blizn/Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на вектор.

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

• Нет информации в разделе 2.7. Александр Сергеевич Антонов (обсуждение) 16:47, 27 октября 2016 (MSK)
• Не заполнен раздел 2.4 описания. Александр Сергеевич Антонов (обсуждение) 15:27, 16 ноября 2016 (MSK)

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

• В разделе 1.4 не нужно дублировать написанное в разделе 1.3, а требуется описание алгоритма на верхнем уровне. Александр Сергеевич Антонов (обсуждение) 16:47, 27 октября 2016 (MSK)
  • Замечание не исправлено. Александр Сергеевич Антонов (обсуждение) 16:04, 2 ноября 2016 (MSK)
• В разделе 2.4 не приведены все параметры запуска теста - какой компилятор, с какими опциями использовался, какие версии библиотек, на каких узлах проводился запуск и т.д. Александр Сергеевич Антонов (обсуждение) 11:09, 30 ноября 2016 (MSK)
• В разделе 2.4 не приведён сам текст использованной в экспериментах реализации алгоритма. Александр Сергеевич Антонов (обсуждение) 11:09, 30 ноября 2016 (MSK)