Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Руководство пользователя 6 Руководство программиста 6 6 Подтверждение корректности 9 9 - файл


скачать (96.2 kb.)


Министерство образования и науки Российской Федерации

Федеральное государственное автономное образовательное учреждение


высшего образования «Национальный исследовательский Нижегородский государственный университет им. Н.И. Лобачевского»


Институт информационных технологий, математики и механики



Умножение разреженных матриц (координатный способ хранения)

Выполнил: студент группы 0833-2

Нижний Новгород

2015 г.


Содержание

Постановка задачи3

Метод решения4

Схема распараллеливания5

Описание программной реализации6

Руководство пользователя6

Руководство программиста66

Подтверждение корректности99

Результаты экспериментов по оценке масштабируемости1010

Заключение 12

Постановка задачи

Необходимо реализовать умножение разреженных матриц, хранящихся в координатном формате.

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

Метод решения

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

Пусть необходимо умножить матрицу (размера ) на матрицу (размера ). Обозначим результат . По определению, .

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




Скачать файл (96.2 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации