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

Материал из Алговики
Перейти к навигации Перейти к поиску

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

1 Пункт 1.1

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

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

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

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

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

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

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

2 Пункт 1.1.1.1

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

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

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

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

3 Пункт 1.1.1.2

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

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

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


4 Пункт 1.1.2

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

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

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


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

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


5 Пункт 1.6

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

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

[math]l[/math] сложений,

[math]l[/math] умножений.


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


6 Пункт 1.8

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

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


7 Пункт 1.10

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

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

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


8 Пункт 2.4

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

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


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

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


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



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

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

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

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