Общая характеристика работы

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

При перемножении матриц элемент результирующей матрицы получается в результате умножения строки матрицы А на столбец матрицы В. Поэтому число элементов в каждой строке матрицы А должно быть равно числу элементов в каждом столбце матрицы В. Иначе матрицы нельзя перемножить.

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

Порядок выполнения работы Расчетно-графическая часть

1.1. Выбрать свой вариант задания на выполнение работы из табл.1.1.

Табл. 1.1. Варианты заданий

№ зада ния	Размерность			№ зада ния	Размерность
	Матрица А	Матрица В			Матрица А	Матрица В
1	5 х 8	8 х 7		11	6 х 8	8 х 7
2	7 х 8	8 х 6		12	8 х 7	7 х 6
3	7 х 6	6 х 8		13	7 х 6	6 х 7
4	6 х 8	8 х 6		14	6 х 7	7 х 6
5	6 х 7	7 х 6		15	8 х 6	6 х 8
6	5 х 6	6 х 8		16	5 х 8	8 х 6
7	8 х 5	5 х 8		17	7 х 8	8 х 5
8	7 х 6	6 х 8		18	5 х 7	7 х 8
9	8 х 7	7 х 8		19	8 х 7	7 х 5
10	6 х 7	7 х 8		20	8 х 6	6 х 7

1.2. Используя свой вариант задания и данные табл.1.2, построить исходные матрицы А и В.

Табл.1.2. Элементы матриц задания

Номера строк	Номера столбцов
	1	2	3	4	5	6	7	8
1	х	х
2	х		х	х
3		х		х	х
4			х		х
5				х		х
6							х
7							х
8								х

х – значащий (ненулевой) элемент;

остальные элементы – нулевые

Например, в задании №8 (табл. 1.1 - выделено цветом) матрицы А[7,6] и В[6,8] будут иметь вид:

Матрица А[7,6]

Номера строк	Номера столбцов
	1	2	3	4	5	6
1	а11	а12	0.	0.	0.	0.
2	а21	0.	а23	а24	0.	0.
3	0.	а32	0.	а34	а35	0.
4	0.	0.	а43	0.	а45	0.
5	0.	0.	0.	а54	0.	а56
6	0.	0.	0.	0.	0.	0.
7	0.	0.	0.	0.	0.	0.

Матрица В[6,8]

Номера строк	Номера столбцов
	1	2	3	4	5	6	7	8
1	b11	b12	0.	0.	0.	0.	0.	0.
2	b21	0.	b23	b24	0.	0.	0.	0.
3	0.	b32	0.	b34	b35	0.	0.	0.
4	0.	0.	b43	0.	b45	0.	0.	0.
5	0.	0.	0.	b54	0.	b56	0.	0.
6	0.	0.	0.	0.	0.		b67	0.

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

Например, в задании №8 матрица А[7,6] содержит две (шестую и седьмую) нулевых строки, а матрица В[6,8] имеет восьмой нулевой столбец (выделено цветом), которые в данном случае можно исключить. Однако следует учесть, что после исключения нулевых строк и столбцов число элементов в каждой строке матрицы А должно быть равно числу элементов в каждом столбце матрицы В. Иначе матрицы нельзя будет перемножить.

В данном случае матрицы А и В преобразуются к виду:

Матрица А [5,6]

Номера строк	Номера столбцов
	1	2	3	4	5	6
1	а11	а12	0.	0.	0.	0.
2	а21	0.	а23	а24	0.	0.
3	0.	а32	0.	а34	а35	0.
4	0.	0.	а43	0.	а45	0.
5	0.	0.	0.	а54	0.	а56

Матрица В [6,7]

Номера строк	Номера столбцов
	1	2	3	4	5	6	7
1	b11	b12	0.	0.	0.	0.	0.
2	b21	0.	b23	b24	0.	0.	0.
3	0.	b32	0.	b34	b35	0.	0.
4	0.	0.	b43	0.	b45	0.	0.
5	0.	0.	0.	b54	0.	b56	0.
6	0.	0.	0.	0.	0.	0.	b67

1.4. Разработать блок-схему (описание) алгоритма решения задачи распараллеливания, т.е. исключения из матриц А и В нулевых строк и столбцов.

1.5. Разработать блок-схему (описание) алгоритма решения задачи перемножения выходных матриц А и В.

1.6. Построить результирующую матрицу С перемножения матриц А и В, полученных в результате распараллеливания. Для данного примера матрица С будет иметь вид:

Матрица С [5,7]

Номера строк	Номера столбцов
	1	2	3	4	5	6	7
1	а11b11+а12b21	а11b12	а11b23	а11b24	0.	0.	0.
2	а21b11	а21b12+а23b32	а24b43	а23b34	а23b35+а24b45	0.	0.
3	а32b21	0.	а32b23 +а34b43	а32b24 +а35b54	а34b45	а35b56	0.
4	0.	0.	0.	а43b34+а45b54	а43b35+	а45b56	0.
5	0.	0.	а54b43	0.	а54b45	0.	а56b67