|
|
Книги-onlineРабота с разреженными матрицами.
Работа с разреженными матрицами.
Конвертация разреженной матрицы из нормальной формы в формат RR(C)O.Процедура конвертирует матрицу содержащуюся в массиве A в формат RR(C)O. Описание формата RR(C)O есть в статье о разреженных матрицах. На выходе получаем: NNZ - число ненулевых элементов матрицы, IA,JA,AN - соответственно массивы используемые в представлении RR(C)O.
Наверх
Описание формата RR(C)U есть в статье о разреженных матрицах. На вход подаются переменные N,M - соответственно количество строк и столбцов матрицы, NNZ - число ненулевых элементов матрицы, IA,JA,AN - массивы используемые в представлении RR(C)U. На выходе получаем массив A содержащий искомую матрицу в нормальной форме. В начале работы алгоритм заполняет массив A нулями, в большинстве языков есть специальные команды, чтобы обнулить некоторый кусок памяти, лучше использовать их, так как обнуление массива в двойном цикле скажется на скоросте работы, особенно в случае, если матрица имеет значительные размеры.
Наверх
Описание формата 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 есть в статье о разреженных матрицах. На вход подаются переменные 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 есть в статье о разреженных матрицах. На вход подаются переменные N,M - соответственно количество строк и столбцов матриц, IA,JA,AN - массивы используемые в представлении RR(C)U матрицы A. IB,JB,AB - массивы используемые в представлении RR(C)U матрицы B. На выходе получаем массивы IC,JC,CN содержащий искомую матрицу в форме RR(C)U. В отличии от предыдущего, данный алгоритм заполняет массивы IC,JC,NC за один проход, к тому же он проверяет возникновение ситуации, когда a[i,j]=-b[i,j] < >0 и не допускает появления в массиве CN нулевых элементов, правда это скажется на скорости работы. Результирующая матрица представлена в формате RR(C)U, т.е. неупорядоченная по столбцам.
Наверх
Алгоритм перемножает матрицы 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, т.е. неупорядоченная по столбцам.
Наверх
Алгоритм перемножает матрицы 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. Принципиально алгоритм основан на тех же соображениях, что и предыдущий, однако данный алгоритм заполняет массивы IC,JC,NC за один проход, к тому же он не допускает появления в массиве CN нулевых элементов. Результирующая матрица представлена в формате RR(C)U, т.е. неупорядоченная по столбцам. Наверх Внимание! Если у вас не получилось найти нужную информацию, используйте рубрикатор или воспользуйтесь поиском . книги по программированию исходники компоненты шаблоны сайтов C++ PHP Delphi скачать |
|