Работа с разреженными матрицами.

Конвертация разреженной матрицы из нормальной формы в формат RR(C)O.

Процедура конвертирует матрицу содержащуюся в массиве A в формат RR(C)O. Описание формата RR(C)O есть в статье о разреженных матрицах. На выходе получаем: NNZ - число ненулевых элементов матрицы, IA,JA,AN - соответственно массивы используемые в представлении RR(C)O. Наверх

Конвертация разреженной матрицы, представленной в формате RR(C)U в нормальную форму.

Описание формата RR(C)U есть в статье о разреженных матрицах. На вход подаются переменные N,M - соответственно количество строк и столбцов матрицы, NNZ - число ненулевых элементов матрицы, IA,JA,AN - массивы используемые в представлении RR(C)U. На выходе получаем массив A содержащий искомую матрицу в нормальной форме. В начале работы алгоритм заполняет массив A нулями, в большинстве языков есть специальные команды, чтобы обнулить некоторый кусок памяти, лучше использовать их, так как обнуление массива в двойном цикле скажется на скоросте работы, особенно в случае, если матрица имеет значительные размеры. Наверх

Транспонирование разреженной матрицы, заданной в формате RR(C)U.

Описание формата RR(C)U есть в статье о разреженных матрицах. На вход подаются переменные N,M - соответственно количество строк и столбцов матрицы, IA,JA,AN - массивы используемые в представлении RR(C)U. На выходе получаем массивы IAT,JAT,ANT содержащий искомую матрицу в форме RR(C)O, количество ненулевых элементов (IA[N]-1 число элементов массивов JA,AN,JAT,ANT) не изменяется, а количество строк исходной матрице равно количеству столбцов транспонированной и наоборот.

Блок-схема является переработкой программы на фортране взятой с сайта библиотеки численного анализа БЧА НИВЦ МГУ. Наверх

Сложение двух матриц, заданных в формате RR(C)U.(1-й способ)

Описание формата RR(C)U есть в статье о разреженных матрицах. На вход подаются переменные N,M - соответственно количество строк и столбцов матриц, IA,JA,AN - массивы используемые в представлении RR(C)U матрицы A. IB,JB,AB - массивы используемые в представлении RR(C)U матрицы B. На выходе получаем массивы IC,JC,CN содержащий искомую матрицу в форме RR(C)U.

Блок-схема является переработкой программ на фортране взятых с сайта библиотеки численного анализа БЧА НИВЦ МГУ.

Алгоритм вначале формирует портрет матрицы С в массивах IC,JC, а затем заполняет массив CN значениями ненулевых элементов матрицы C. Можно исправить алгоритм сделав так, чтобы формирование портрета матрицы и заполнение массива CN проводилось одновременно, именно так устроен алгоритм, предъявленный ниже.

Есть одна маленькая проблема в работе алгоритма, а именно, если для некоторых i,j выполняется a[i,j]=-b[i,j] < >0, то в представлении результирующей матрицы элемент c[i,j] должен отсутствовать, но данный алгоритм не отслеживает эту ситуацию, поэтому возможно возникновение нулевых элементов в массиве СN.

Возникает вопрос для чего необходимо разбиение алгоритма сложения на два этапа? Все дело в том, что результат получается в формате RR(C)U, т.е. неупорядоченный по столбцам, вне зависимости от того были ли исходные матрицы в формате RR(C)O или нет, но поскольку вначале мы получаем портрет результирующей матрицы, то если после этого привести полученный портрет к формату RR(C)O, например, дважды выполнив алгоритм транспонирования матрицы, учитывая только портрет С, а уже затем заполнять массив CN, то в результате матрица С будет представлена в формате RR(C)O. Наверх

Сложение двух матриц, заданных в формате RR(C)U.(2-й способ)

В отличии от предыдущего, данный алгоритм заполняет массивы IC,JC,NC за один проход, к тому же он проверяет возникновение ситуации, когда a[i,j]=-b[i,j] < >0 и не допускает появления в массиве CN нулевых элементов, правда это скажется на скорости работы.

Результирующая матрица представлена в формате RR(C)U, т.е. неупорядоченная по столбцам. Наверх

Умножение двух матриц, заданных в формате RR(C)U.(1-й способ)

Алгоритм перемножает матрицы A размера n*m и B (m*q), заданные в формате RR(C)U и результат помещает в матрицу C, описание формата RR(C)U есть в статье о разреженных матрицах. На вход подаются переменные n,m,q - соответствeющие размерности матриц, IA,JA,AN - массивы используемые в представлении RR(C)U матрицы A. IB,JB,AB - массивы используемые в представлении RR(C)U матрицы B. На выходе получаем массивы IC,JC,CN содержащий искомую матрицу в форме RR(C)U.

Известно, что элементы матрицы С получаются по формулам:

	сik=ai1b1k+...+aimbmk для i=1..n;k=1..q

Эта формула выражает элемент ci k как скалярное произведение i-й строки матрицы A на k- й столбец матрицы B. Однако поскольку матрица B задана строчным форматом, то к ее столбцам нет непосредственного доступа. Эту трудность можно обойти измененив порядок вычислений попарных произведений. При вычислении cik: при фиксированных i и j элемент ai j умножается на все элементы bjk j -й строки матрицы B; полученные произведения прибавляются к соответствующим компонентам вещественного вспомогательного массива X, начальные значения которых равны нулю. Когда таким образом обработаны все элементы i-й строки матрицы A, массив X содержит полную i-ю строку матрицы C.

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

Результирующая матрица представлена в формате RR(C)U, т.е. неупорядоченная по столбцам. Наверх

Умножение двух матриц, заданных в формате RR(C)U.(2-й способ)

Принципиально алгоритм основан на тех же соображениях, что и предыдущий, однако данный алгоритм заполняет массивы IC,JC,NC за один проход, к тому же он не допускает появления в массиве CN нулевых элементов.

Результирующая матрица представлена в формате RR(C)U, т.е. неупорядоченная по столбцам. Наверх