Matrix-vector product. Matrix multiplication: examples, algorithm of actions, properties of the product

Definition 1

The product of matrices (C = AB) is an operation only for matched matrices A and B, in which the number of columns of matrix A is equal to the number of rows of matrix B:

C ⏟ m × n = A ⏟ m × p × B ⏟ p × n

Example 1

Given matrices:

A = a (i j) sizes m × n;
B = b (i j) sizes p × n

Matrix C, the elements c i j of which are calculated by the following formula:

c i j = a i 1 × b 1 j + a i 2 × b 2 j +. ... ... + a i p × b p j, i = 1,. ... ... m, j = 1,. ... ... m

Example 2

We calculate the products AB = BA:

A = 1 2 1 0 1 2, B = 1 0 0 1 1 1

Solution using the matrix multiplication rule:

A ⏟ 2 × 3 × B ⏟ 3 × 2 = 1 2 1 0 1 2 × 1 0 0 1 1 1 = 1 × 1 + 2 × 0 + 1 × 1 1 × 0 + 2 × 1 + 1 × 1 0 × 1 + 1 × 0 + 2 × 1 0 × 0 + 1 × 1 + 2 × 1 = = 2 3 2 3 ⏟ 2 × 2

B ⏟ 3 × 2 × A ⏟ 2 × 3 = 1 0 0 1 1 1 × 1 2 1 0 1 2 = 1 × 1 + 0 × 0 1 × 2 + 0 × 1 1 × 1 + 0 × 2 0 × 1 + 1 × 0 0 × 2 + 1 × 1 0 × 1 + 1 × 2 1 × 1 + 1 × 0 1 × 2 + 1 × 1 1 × 1 + 1 × 2 = 1 2 1 0 1 2 1 3 3 ⏟ 3 × 3

The product A B and B A are found, but they are matrices of different sizes: A B is not equal to B A.

Matrix multiplication properties

Matrix multiplication properties:

(A B) C = A (B C) - associativity of matrix multiplication;
А (В + С) = А В + А С - distributivity of multiplication;
(A + B) C = A C + B C - distributivity of multiplication;
λ (А В) = (λ А) В

Example 1

Checking property # 1: (A B) C = A (B C):

(A × B) × A = 1 2 3 4 × 5 6 7 8 × 1 0 0 2 = 19 22 43 50 × 1 0 0 2 = 19 44 43 100,

A (B × C) = 1 2 3 4 × 5 6 7 8 1 0 0 2 = 1 2 3 4 × 5 12 7 16 = 19 44 43 100.

Example 2

Checking property # 2: A (B + C) = A B + A C:

A × (B + C) = 1 2 3 4 × 5 6 7 8 + 1 0 0 2 = 1 2 3 4 × 6 6 7 10 = 20 26 46 58,

A B + A C = 1 2 3 4 × 5 6 7 8 + 1 2 3 4 × 1 0 0 2 = 19 22 43 50 + 1 4 3 8 = 20 26 46 58.

Product of three matrices

The product of three matrices A B C is calculated in 2 ways:

find AB and multiply by C: (AB) C;
or find first B C, and then multiply A (B C).

Example 3

Multiply matrices in 2 ways:

4 3 7 5 × - 28 93 38 - 126 × 7 3 2 1

Algorithm of actions:

find the product of 2 matrices;
then find the product of 2 matrices again.

1). A B = 4 3 7 5 × - 28 93 38 - 126 = 4 (- 28) + 3 × 38 4 × 93 + 3 (- 126) 7 (- 28) + 5 × 38 7 × 93 + 5 (- 126 ) = 2 - 6 - 6 21

2). А В С = (А В) С = 2 - 6 - 6 21 7 3 2 1 = 2 × 7 - 6 × 2 2 × 3 - 6 × 1 - 6 × 7 + 21 × 2 - 6 × 3 + 21 × 1 = 2 0 0 3.

We use the formula A B C = (A B) C:

1). In С = - 28 93 38 - 126 7 3 2 1 = - 28 × 7 + 93 × 2 - 28 × 3 + 93 × 1 38 × 7 - 126 × 2 38 × 3 - 126 × 1 = - 10 9 14 - 12

2). A B C = (A B) C = 7 3 2 1 - 10 9 14 - 12 = 4 (- 10) + 3 × 14 4 × 9 + 3 (- 12) 7 (- 10) + 5 × 14 7 × 9 + 5 (- 12) = 2 0 0 3

Answer: 4 3 7 5 - 28 93 38 - 126 7 3 2 1 = 2 0 0 3

Multiplying a Matrix by a Number

Definition 2

The product of the matrix A by the number k is the matrix B = A k of the same size, which is obtained from the original by multiplying by a given number of all its elements:

b i, j = k × a i, j

Properties of multiplying a matrix by a number:

1 × A = A
0 × A = null matrix
k (A + B) = k A + k B
(k + n) A = k A + n A
(k × n) × A = k (n × A)

Example 4

Find the product of the matrix A = 4 2 9 0 by 5.

5 A = 5 4 2 9 0 5 × 4 5 × 2 5 × 9 5 × 0 = 20 10 45 0

Matrix-vector multiplication

Definition 3

To find the product of a matrix and a vector, you need to multiply according to the "row by column" rule:

if you multiply a matrix by a column vector, the number of columns in the matrix must match the number of rows in the column vector;
the result of multiplying a column vector is only a column vector:

А В = а 11 а 12 ⋯ а 1 n а 21 а 22 ⋯ а 2 n ⋯ ⋯ ⋯ ⋯ а m 1 а m 2 ⋯ а mnb 1 b 2 ⋯ b 1 n = a 11 × b 1 + a 12 × b 2 + ⋯ + a 1 n × bna 21 × b 1 + a 22 × b 2 + ⋯ + a 2 n × bn ⋯ ⋯ ⋯ ⋯ am 1 × b 1 + am 2 × b 2 + ⋯ + amn × bn = c 1 c 2 ⋯ c 1 m

if you multiply a matrix by a row vector, then the matrix being multiplied must be exclusively a column vector, and the number of columns must match the number of columns in the row vector:

А В = а а ⋯ а bb ⋯ b = a 1 × b 1 a 1 × b 2 ⋯ a 1 × bna 2 × b 1 a 2 × b 2 ⋯ a 2 × bn ⋯ ⋯ ⋯ ⋯ an × b 1 an × b 2 ⋯ an × bn = c 11 c 12 ⋯ c 1 nc 21 c 22 ⋯ c 2 n ⋯ ⋯ ⋯ ⋯ cn 1 cn 2 ⋯ cnn

Example 5

Find the product of the matrix A and the column vector B:

А В = 2 4 0 - 2 1 3 - 1 0 1 1 2 - 1 = 2 × 1 + 4 × 2 + 0 × (- 1) - 2 × 1 + 1 × 2 + 3 × (- 1) - 1 × 1 + 0 × 2 + 1 × (- 1) = 2 + 8 + 0 - 2 + 2 - 3 - 1 + 0 - 1 = 10 - 3 - 2

Example 6

Find the product of the matrix A and the row vector B:

A = 3 2 0 - 1, B = - 1 1 0 2

А В = 3 2 0 1 × - 1 1 0 2 = 3 × (- 1) 3 × 1 3 × 0 3 × 2 2 × (- 1) 2 × 1 2 × 0 2 × 2 0 × (- 1) 0 × 1 0 × 0 0 × 2 1 × (- 1) 1 × 1 1 × 0 1 × 2 = - 3 3 0 6 - 2 2 0 4 0 0 0 0 - 1 1 0 2

Answer: A B = - 3 3 0 6 - 2 2 0 4 0 0 0 0 - 1 1 0 2

If you notice an error in the text, please select it and press Ctrl + Enter

MatLab system performs mathematical operations on matrices and vectors quite simply. Let us first consider the simple operations of addition and multiplication of matrices and vectors. Let there be given two vectors

a =; % row vector
b =; % column vector

then the multiplication of these two vectors can be written as

c = a * b; % c = 1 + 2 + 3 + 4 + 5 = 16
d = b * a; % d - 5x5 matrix

In accordance with operations on vectors, multiplying a row vector by a column vector gives a number, and multiplying a column vector by a row vector gives a two-dimensional matrix, which is the result of the calculations in the given example, i.e.

Addition and subtraction of two vectors is written as follows

a1 =;
a2 =;
c = a1 + a2; % c =;
c = a2-a1; % c =;

Note that addition and subtraction operations can be performed between two column vectors or two row vectors. Otherwise MatLab will display an error message, because vectors of different types cannot be added. This is the case with all unacceptable arithmetic operations: if it is impossible to calculate them, the MatLab system will report an error and the program will be completed on the corresponding line.

The operations of multiplication and addition between matrices are performed in a similar way:

A =;
B = ones (3);
C = A + B; % addition of two matrices of the same size
D = A + 5; % addition of a matrix and a number
E = A * B; % multiplication of matrix A by B
F = B * A; % multiplication of matrix B by A
G = 5 * A; % matrix multiplication by number

The operations of calculating the inverse matrix, as well as the transposition of matrices and vectors, are written as follows:

a =; % row vector
b = a '; % column vector formed by
% by transposing the row vector a.
A =; % matrix 3x3 elements
B = a * A; % B = - row vector
C = A * b; % C = - column vector
D = a * A * a '; % D = 45 - the number, the sum of the elements of the matrix A
E = A '; % E - transposed matrix A
F = inv (A); % F - inverse matrix A
G = A ^ -1; % G - inverse matrix A

From the above example, you can see that the operation of transposing matrices and vectors is denoted by the symbol '(apostrophe), which is placed after the name of the vector or matrix. Computing the inverse of a matrix can be done by calling the inv () function or by raising the matrix to the -1 power. The result in both cases will be the same, and the two calculation methods are done for ease of use when implementing different algorithms.

If in the process of calculations it is required to element-wise multiply, divide or raise the elements of a vector or matrix to a power, then the operators are used for this:

. * - element-wise multiplication;
./ and. \ - element-wise divisions;
. ^ - element-wise exponentiation.

Let's consider the work of these operators in the following example.

a =; % row vector
b =; % row vector
c = a. * b; % c =
A = ones (3); % 3x3 matrix consisting of ones
B =; % matrix 3x3
C = A. * B; % a 3x3 matrix consisting of
D = A./B; % a 3x3 matrix consisting of
E = A. \ B; % a 3x3 matrix consisting of
F = A. ^ 2; % squaring the elements of matrix A

At the end of this section, we will consider several functions that are useful when working with vectors and matrices.

To find the maximum value of a vector element, the standard max () function is used, which returns the found maximum value of an element and its position (index):

a =;
= max (a); % v = 6, i = 2;

v = max (a); % v = 6;

The above example shows two different ways to call the max () function. In the first case, both the maximum value of the element and its index in the vector are determined, and in the second - only the maximum value of the element.

In the case of matrices, this function defines the maximum values in the columns, as shown in the example below:

A =;
= max (A); % V =, I =
V = max (A); % V =

The full syntax of the max () function can be found by typing the command in the MatLab command window

help<название функции>

The min () function works in a similar way, which determines the minimum value of an element of a vector or matrix and its index.

Another useful function for working with matrices and vectors is the sum () function, which calculates the sum of the values of the elements of a vector or matrix columns:

a =;
s = sum (a); % s = 3 + 5 + 4 + 2 + 1 = 15
A =;
S1 = sum (A); % S1 =
S2 = sum (sum (A)); % S2 = 39

When calculating the sum S2, the sum of the values of the elements of the matrix A is first calculated by columns, and then, by rows. As a result, the variable S2 contains the sum of the values of all elements of the matrix A.

To sort the values of elements of a vector or matrix in ascending or descending order, use the sort () function as follows:

a =;

b1 = sort (a); % b1 =
b2 = sort (a, ‘descend’); % b2 =
b3 = sort (a, 'ascend'); % b3 =

for matrices

A =;
B1 = sort (A); % B1 =
B2 = sort (A, ‘descend’); % B2 =

In many practical tasks it is often required to find a specific element in a vector or matrix. This can be done using the standard find () function, which takes as an argument a condition according to which the required elements are found, for example:

a =;
b1 = find (a == 2); % b1 = 4 - index of element 2
b2 = find (a ~ = 2); % b2 = - indices without 2
b3 = find (a> 3); % b3 =

In the above example, the symbol '==' means a check for equality, and the symbol '~ =' performs a check for inequality of the values of the elements of the vector a. More details about these operators will be described in the section on conditional operators.

Another useful function for working with vectors and matrices is the mean () function for calculating the mean arithmetic value which works like this:

a =;
m = mean (a); % m = 3
A =;
M1 = mean (A); % M1 =
M2 = mean (mean (A)); % M2 = 4.333

Each vector can be thought of as a single column or single row matrix. A one-column matrix will be called a column vector, and a one-row matrix will be called a row vector.

If the A is an m * n matrix, then the column vector b is of size n, and the vector row b is of size m.

Thus, to multiply a matrix by a vector, the vector must be viewed as a column vector. When multiplying a vector by a matrix, it must be treated as a row vector.

Multiply matrix

on a complex vector

We get the result

As you can see, given the constant dimension of the vector, we can have two solutions.

I would like to draw your attention to the fact that the matrix in the first and second versions, despite the same values, are completely different (have different dimensions)

In the first case, the vector is considered as a column and then it is necessary multiply matrix by vector, and in the second case we have a row vector and then we have product of a vector by a matrix.

This bot also multiplies vectors and matrices that have complex values. Powered by the more complete calculator Complex matrix multiplication online

Matrix-vector multiplication properties

Matrix

Vector column

Row vector

Arbitrary number

1. The product of the matrix by the sum of the column vectors is equal to the sum of the products of the matrix by each of the vectors

2. The product of the sum of row vectors by the matrix is equal to the sum of the products of vectors by the matrix

3. The common factor of the vector can be moved outside the product of the matrix by the vector / vector by the matrix

4. The product of a row vector by the product of a matrix and a column vector is equivalent to the product of a product of a row vector by a matrix and a column vector.

So, in the previous lesson, we discussed the rules for adding and subtracting matrices. These are such simple operations that most students understand them literally on the fly.

However, you rejoice early. The freebie is over - let's move on to multiplication. I will warn you right away: multiplying two matrices is not at all multiplying the numbers in cells with the same coordinates, as you might think. Everything is much more fun here. And you have to start with preliminary definitions.

Consistent matrices

One of the most important characteristics of a matrix is its size. We have already talked about this a hundred times: the notation $ A = \ left [m \ times n \ right] $ means that the matrix contains exactly $ m $ rows and $ n $ columns. We have already discussed how not to confuse rows with columns. Now something else is important.

Definition. Matrices of the form $ A = \ left [m \ times n \ right] $ and $ B = \ left [n \ times k \ right] $, in which the number of columns in the first matrix is the same as the number of rows in the second, are called consistent.

Once again: the number of columns in the first matrix is equal to the number of rows in the second! From here we get two conclusions at once:

The order of the matrices is important to us. For example, matrices $ A = \ left [3 \ times 2 \ right] $ and $ B = \ left [2 \ times 5 \ right] $ are consistent (2 columns in the first matrix and 2 rows in the second), but vice versa - matrices $ B = \ left [2 \ times 5 \ right] $ and $ A = \ left [3 \ times 2 \ right] $ - are no longer matched (5 columns in the first matrix are like 3 rows in the second ).
Consistency is easy to check if you write out all the dimensions one after the other. For example from the previous paragraph: "3 2 2 5" - in the middle are the same numbers, so the matrices are consistent. But "2 5 3 2" - are not consistent, because in the middle there are different numbers.

In addition, the captain of the obviousness seems to be hinting that square matrices of the same size $ \ left [n \ times n \ right] $ are always consistent.

In mathematics, when the order of enumeration of objects is important (for example, in the above definition, the order of matrices is important), one often speaks of ordered pairs. We met with them at school: I think it's a no brainer that the coordinates $ \ left (1; 0 \ right) $ and $ \ left (0; 1 \ right) $ set different points on the plane.

So: coordinates are also ordered pairs that are made up of numbers. But nothing prevents from composing such a pair of matrices. Then we can say: "An ordered pair of matrices $ \ left (A; B \ right) $ is consistent if the number of columns in the first matrix is the same as the number of rows in the second."

Well, so what?

Definition of multiplication

Consider two matched matrices: $ A = \ left [m \ times n \ right] $ and $ B = \ left [n \ times k \ right] $. And define the multiplication operation for them.

Definition. The product of two matched matrices $ A = \ left [m \ times n \ right] $ and $ B = \ left [n \ times k \ right] $ is a new matrix $ C = \ left [m \ times k \ right] $, the elements of which are calculated by the formula:

\ [\ begin (align) & ((c) _ (i; j)) = ((a) _ (i; 1)) \ cdot ((b) _ (1; j)) + ((a) _ (i; 2)) \ cdot ((b) _ (2; j)) + \ ldots + ((a) _ (i; n)) \ cdot ((b) _ (n; j)) = \\ & = \ sum \ limits_ (t = 1) ^ (n) (((a) _ (i; t)) \ cdot ((b) _ (t; j))) \ end (align) \]

Such a product is denoted in a standard way: $ C = A \ cdot B $.

Those who see this definition for the first time have two questions at once:

What is this fierce game?
Why is it so difficult?

Well, first things first. Let's start with the first question. What do all these indices mean? And how not to be mistaken when working with real matrices?

First of all, note that a long line for calculating $ ((c) _ (i; j)) $ (I specially put a semicolon between the indices so as not to get confused, but in general they do not need to be put - I myself got tired of typing the formula in the definition) actually boils down to a simple rule:

Take the $ i $ th row in the first matrix;
Take the $ j $ th column in the second matrix;
We get two sequences of numbers. We multiply the elements of these sequences with the same numbers, and then add the resulting products.

This process is easy to understand from the picture:

Scheme for multiplying two matrices

Once again: we fix the row $ i $ in the first matrix, the column $ j $ in the second matrix, multiply the elements with the same numbers, and then add the resulting products - we get $ ((c) _ (ij)) $. And so for all $ 1 \ le i \ le m $ and $ 1 \ le j \ le k $. Those. in total there will be $ m \ times k $ such "perversions".

In fact, we have already met with matrix multiplication in school curriculum, only in a very truncated form. Let vectors be given:

\ [\ begin (align) & \ vec (a) = \ left (((x) _ (a)); ((y) _ (a)); ((z) _ (a)) \ right); \\ & \ overrightarrow (b) = \ left (((x) _ (b)); ((y) _ (b)); ((z) _ (b)) \ right). \\ \ end (align) \]

Then their scalar product will be exactly the sum of pairwise products:

\ [\ overrightarrow (a) \ times \ overrightarrow (b) = ((x) _ (a)) \ cdot ((x) _ (b)) + ((y) _ (a)) \ cdot ((y ) _ (b)) + ((z) _ (a)) \ cdot ((z) _ (b)) \]

Basically, back in the years when the trees were greener and the sky brighter, we simply multiplied the row vector $ \ overrightarrow (a) $ by the column vector $ \ overrightarrow (b) $.

Nothing has changed today. It's just that now there are more of these row vectors and columns.

But enough theory! Let's take a look at real-life examples. And let's start with the simplest case - square matrices.

Multiplication of square matrices

Task 1. Perform multiplication:

\ [\ left [\ begin (array) (* (35) (r)) 1 & 2 \\ -3 & 4 \\\ end (array) \ right] \ cdot \ left [\ begin (array) (* (35) (r)) -2 & 4 \\ 3 & 1 \\\ end (array) \ right] \]

Solution. So, we have two matrices: $ A = \ left [2 \ times 2 \ right] $ and $ B = \ left [2 \ times 2 \ right] $. It is clear that they are consistent (square matrices of the same size are always consistent). Therefore, we perform the multiplication:

\ [\ begin (align) & \ left [\ begin (array) (* (35) (r)) 1 & 2 \\ -3 & 4 \\\ end (array) \ right] \ cdot \ left [\ begin (array) (* (35) (r)) -2 & 4 \\ 3 & 1 \\\ end (array) \ right] = \ left [\ begin (array) (* (35) (r)) 1 \ cdot \ left (-2 \ right) +2 \ cdot 3 & 1 \ cdot 4 + 2 \ cdot 1 \\ -3 \ cdot \ left (-2 \ right) +4 \ cdot 3 & -3 \ cdot 4 + 4 \ cdot 1 \\\ end (array) \ right] = \\ & = \ left [\ begin (array) (* (35) (r)) 4 & 6 \\ 18 & -8 \\\ end (array) \ right]. \ end (align) \]

That's all!

Answer: $ \ left [\ begin (array) (* (35) (r)) 4 & 6 \\ 18 & -8 \\\ end (array) \ right] $.

Task 2. Perform multiplication:

\ [\ left [\ begin (matrix) 1 & 3 \\ 2 & 6 \\\ end (matrix) \ right] \ cdot \ left [\ begin (array) (* (35) (r)) 9 & 6 \\ -3 & -2 \\\ end (array) \ right] \]

Solution. Again matched matrices, so we perform the following actions: \ [\]

\ [\ begin (align) & \ left [\ begin (matrix) 1 & 3 \\ 2 & 6 \\\ end (matrix) \ right] \ cdot \ left [\ begin (array) (* (35) ( r)) 9 & 6 \\ -3 & -2 \\\ end (array) \ right] = \ left [\ begin (array) (* (35) (r)) 1 \ cdot 9 + 3 \ cdot \ left (-3 \ right) & 1 \ cdot 6 + 3 \ cdot \ left (-2 \ right) \\ 2 \ cdot 9 + 6 \ cdot \ left (-3 \ right) & 2 \ cdot 6 + 6 \ cdot \ left (-2 \ right) \\\ end (array) \ right] = \\ & = \ left [\ begin (matrix) 0 & 0 \\ 0 & 0 \\\ end (matrix) \ right] ... \ end (align) \]

As you can see, we got a matrix filled with zeros

Answer: $ \ left [\ begin (matrix) 0 & 0 \\ 0 & 0 \\\ end (matrix) \ right] $.

From the examples given, it is obvious that matrix multiplication is not such a difficult operation. At least for 2 by 2 square matrices.

In the course of calculations, we compiled an intermediate matrix, where we wrote directly which numbers are included in this or that cell. This is exactly what you should do when solving real problems.

Basic properties of the matrix product

In a nutshell. Matrix multiplication:

Non-commutative: $ A \ cdot B \ ne B \ cdot A $ in general. There are, of course, special matrices for which the equality $ A \ cdot B = B \ cdot A $ (for example, if $ B = E $ is the identity matrix), but in the vast majority of cases this does not work;
Associative: $ \ left (A \ cdot B \ right) \ cdot C = A \ cdot \ left (B \ cdot C \ right) $. There are no options here: the matrices standing next to each other can be multiplied without worrying about what is to the left and to the right of these two matrices.
Distributive: $ A \ cdot \ left (B + C \ right) = A \ cdot B + A \ cdot C $ and $ \ left (A + B \ right) \ cdot C = A \ cdot C + B \ cdot C $ (due to the noncommutativity of the product, we have to write separately the distributivity on the right and on the left.

And now - everything is the same, but in more detail.

Matrix multiplication is a lot like classical number multiplication. But there are differences, the most important of which is that matrix multiplication is generally non-commutative.

Consider again the matrices from Problem 1. We already know their direct product:

\ [\ left [\ begin (array) (* (35) (r)) 1 & 2 \\ -3 & 4 \\\ end (array) \ right] \ cdot \ left [\ begin (array) (* (35) (r)) -2 & 4 \\ 3 & 1 \\\ end (array) \ right] = \ left [\ begin (array) (* (35) (r)) 4 & 6 \\ 18 & -8 \\\ end (array) \ right] \]

But if we swap the matrices, we get a completely different result:

\ [\ left [\ begin (array) (* (35) (r)) -2 & 4 \\ 3 & 1 \\\ end (array) \ right] \ cdot \ left [\ begin (array) (* (35) (r)) 1 & 2 \\ -3 & 4 \\\ end (array) \ right] = \ left [\ begin (matrix) -14 & 4 \\ 0 & 10 \\\ end (matrix ) \ right] \]

It turns out that $ A \ cdot B \ ne B \ cdot A $. In addition, the multiplication operation is only defined for matrices $ A = \ left [m \ times n \ right] $ and $ B = \ left [n \ times k \ right] $, but no one guaranteed that they would remain consistent. if you swap them. For example, the matrices $ \ left [2 \ times 3 \ right] $ and $ \ left [3 \ times 5 \ right] $ are quite compatible in the indicated order, but the same matrices $ \ left [3 \ times 5 \ right] The $ and $ \ left [2 \ times 3 \ right] $, written in reverse order, are no longer matched. Sadness. :(

Among square matrices given size There are always $ n $ that give the same result when multiplied in forward or backward order. How to describe all such matrices (and how many in general) is a topic for a separate lesson. We won't talk about that today. :)

However, matrix multiplication is associative:

\ [\ left (A \ cdot B \ right) \ cdot C = A \ cdot \ left (B \ cdot C \ right) \]

Therefore, when you need to multiply several matrices in a row at once, it is not at all necessary to do it right through: it is quite possible that some adjacent matrices give an interesting result when multiplied. For example, a null matrix, as in Problem 2, discussed above.

In real problems, most often you have to multiply square matrices of size $ \ left [n \ times n \ right] $. The set of all such matrices is denoted by $ ((M) ^ (n)) $ (that is, the notation $ A = \ left [n \ times n \ right] $ and \ mean the same thing), and it must contain matrix $ E $, which is called the identity matrix.

Definition. An identity matrix of size $ n $ is such a matrix $ E $ that for any square matrix $ A = \ left [n \ times n \ right] $ the following equality holds:

Such a matrix always looks the same: there are ones on the main diagonal, and zeros in all other cells.

\ [\ begin (align) & A \ cdot \ left (B + C \ right) = A \ cdot B + A \ cdot C; \\ & \ left (A + B \ right) \ cdot C = A \ cdot C + B \ cdot C. \\ \ end (align) \]

In other words, if you need to multiply one matrix by the sum of two others, then you can multiply it by each of these "other two", and then add the results. In practice, we usually have to perform the opposite operation: we notice the same matrix, put it outside the parenthesis, perform addition and thereby simplify our life. :)

Note: to describe distributivity, we had to write two formulas: where the sum is in the second factor and where the sum is in the first. This is precisely due to the fact that matrix multiplication is non-commutative (and in general, in non-commutative algebra there are a lot of jokes that don't even come to mind when working with ordinary numbers). And if, for example, you need to describe this property on the exam, then be sure to write both formulas, otherwise the teacher may get a little angry.

Okay, these were all square matrix fairy tales. What about rectangular ones?

The case of rectangular matrices

But nothing - everything is the same as with square ones.

Task 3. Perform the multiplication:

\ [\ left [\ begin (matrix) \ begin (matrix) 5 \\ 2 \\ 3 \\\ end (matrix) & \ begin (matrix) 4 \\ 5 \\ 1 \\\ end (matrix) \ \\ end (matrix) \ right] \ cdot \ left [\ begin (array) (* (35) (r)) -2 & 5 \\ 3 & 4 \\\ end (array) \ right] \]

Solution. We have two matrices: $ A = \ left [3 \ times 2 \ right] $ and $ B = \ left [2 \ times 2 \ right] $. Let's write out the numbers denoting the sizes in a row:

As you can see, the central two numbers coincide. This means that the matrices are consistent, and they can be multiplied. And at the output we get the matrix $ C = \ left [3 \ times 2 \ right] $:

\ [\ begin (align) & \ left [\ begin (matrix) \ begin (matrix) 5 \\ 2 \\ 3 \\\ end (matrix) & \ begin (matrix) 4 \\ 5 \\ 1 \\ \ end (matrix) \\\ end (matrix) \ right] \ cdot \ left [\ begin (array) (* (35) (r)) -2 & 5 \\ 3 & 4 \\\ end (array) \ right] = \ left [\ begin (array) (* (35) (r)) 5 \ cdot \ left (-2 \ right) +4 \ cdot 3 & 5 \ cdot 5 + 4 \ cdot 4 \\ 2 \ cdot \ left (-2 \ right) +5 \ cdot 3 & 2 \ cdot 5 + 5 \ cdot 4 \\ 3 \ cdot \ left (-2 \ right) +1 \ cdot 3 & 3 \ cdot 5 + 1 \ cdot 4 \\\ end (array) \ right] = \\ & = \ left [\ begin (array) (* (35) (r)) 2 & 41 \\ 11 & 30 \\ -3 & 19 \ \\ end (array) \ right]. \ end (align) \]

Everything is clear: the final matrix has 3 rows and 2 columns. Quite to itself $ = \ left [3 \ times 2 \ right] $.

Answer: $ \ left [\ begin (array) (* (35) (r)) \ begin (array) (* (35) (r)) 2 \\ 11 \\ -3 \\\ end (array) & \ begin (matrix) 41 \\ 30 \\ 19 \\\ end (matrix) \\\ end (array) \ right] $.

Now let's look at one of the best training tasks for those who are just starting to work with matrices. In it, it is necessary not only to multiply some two tables, but first to determine: is such a multiplication permissible?

Problem 4. Find all possible pairwise products of matrices:

\\]; $ B = \ left [\ begin (matrix) \ begin (matrix) 0 \\ 2 \\ 0 \\ 4 \\\ end (matrix) & \ begin (matrix) 1 \\ 0 \\ 3 \\ 0 \ \\ end (matrix) \\\ end (matrix) \ right] $; $ C = \ left [\ begin (matrix) 0 & 1 \\ 1 & 0 \\\ end (matrix) \ right] $.

Solution. First, let's write down the sizes of the matrices:

\; \ B = \ left [4 \ times 2 \ right]; \ C = \ left [2 \ times 2 \ right] \]

We get that the matrix $ A $ can be matched only with the matrix $ B $, since the number of columns in $ A $ is 4, and only $ B $ has this number of rows. Therefore, we can find the product:

\\ cdot \ left [\ begin (array) (* (35) (r)) 0 & 1 \\ 2 & 0 \\ 0 & 3 \\ 4 & 0 \\\ end (array) \ right] = \ left [\ begin (array) (* (35) (r)) - 10 & 7 \\ 10 & 7 \\\ end (array) \ right] \]

I suggest the reader to perform the intermediate steps independently. I will only note that it is better to determine the size of the resulting matrix in advance, before any calculations:

\\ cdot \ left [4 \ times 2 \ right] = \ left [2 \ times 2 \ right] \]

In other words, we simply remove the "transit" coefficients that ensured consistency of the matrices.

What other options are there? Of course, you can find $ B \ cdot A $, because $ B = \ left [4 \ times 2 \ right] $, $ A = \ left [2 \ times 4 \ right] $, so the ordered pair $ \ left (B ; A \ right) $ is consistent, and the dimension of the product will be:

\\ cdot \ left [2 \ times 4 \ right] = \ left [4 \ times 4 \ right] \]

In short, the output will be the matrix $ \ left [4 \ times 4 \ right] $, the coefficients of which are easily calculated:

\\ cdot \ left [\ begin (array) (* (35) (r)) 1 & -1 & 2 & -2 \\ 1 & 1 & 2 & 2 \\\ end (array) \ right] = \ left [\ begin (array) (* (35) (r)) 1 & 1 & 2 & 2 \\ 2 & -2 & 4 & -4 \\ 3 & 3 & 6 & 6 \\ 4 & -4 & 8 & -8 \\\ end (array) \ right] \]

Obviously, you can reconcile another $ C \ cdot A $ and $ B \ cdot C $ - that's all. Therefore, we simply write down the resulting works:

It was easy.:)

Answer: $ AB = \ left [\ begin (array) (* (35) (r)) -10 & 7 \\ 10 & 7 \\\ end (array) \ right] $; $ BA = \ left [\ begin (array) (* (35) (r)) 1 & 1 & 2 & 2 \\ 2 & -2 & 4 & -4 \\ 3 & 3 & 6 & 6 \\ 4 & -4 & 8 & -8 \\\ end (array) \ right] $; $ CA = \ left [\ begin (array) (* (35) (r)) 1 & 1 & 2 & 2 \\ 1 & -1 & 2 & -2 \\\ end (array) \ right] $; $ BC = \ left [\ begin (array) (* (35) (r)) 1 & 0 \\ 0 & 2 \\ 3 & 0 \\ 0 & 4 \\\ end (array) \ right] $.

In general, I highly recommend doing this task yourself. And one more similar task, which is in homework... These seemingly simple thoughts will guide you through all the key steps in matrix multiplication.

But the story doesn't end there. Let's move on to special cases of multiplication. :)

Row vectors and column vectors

One of the most common matrix operations is multiplication by a matrix with one row or one column.

Definition. A column vector is a $ \ left [m \ times 1 \ right] $ matrix, i.e. consisting of several rows and only one column.

A row vector is a $ \ left [1 \ times n \ right] $ matrix, i.e. consisting of one row and several columns.

In fact, we have already met these objects. For example, an ordinary 3D vector from stereometry $ \ overrightarrow (a) = \ left (x; y; z \ right) $ is nothing more than a row vector. From a theoretical point of view, there is almost no difference between rows and columns. You need to be careful only when coordinating with the surrounding multiplier matrices.

Task 5. Perform multiplication:

\ [\ left [\ begin (array) (* (35) (r)) 2 & -1 & 3 \\ 4 & 2 & 0 \\ -1 & 1 & 1 \\\ end (array) \ right] \ cdot \ left [\ begin (array) (* (35) (r)) 1 \\ 2 \\ -1 \\\ end (array) \ right] \]

Solution. Before us is the product of matched matrices: $ \ left [3 \ times 3 \ right] \ cdot \ left [3 \ times 1 \ right] = \ left [3 \ times 1 \ right] $. Let's find this work:

\ [\ left [\ begin (array) (* (35) (r)) 2 & -1 & 3 \\ 4 & 2 & 0 \\ -1 & 1 & 1 \\\ end (array) \ right] \ cdot \ left [\ begin (array) (* (35) (r)) 1 \\ 2 \\ -1 \\\ end (array) \ right] = \ left [\ begin (array) (* (35 ) (r)) 2 \ cdot 1+ \ left (-1 \ right) \ cdot 2 + 3 \ cdot \ left (-1 \ right) \\ 4 \ cdot 1 + 2 \ cdot 2 + 0 \ cdot 2 \ \ -1 \ cdot 1 + 1 \ cdot 2 + 1 \ cdot \ left (-1 \ right) \\\ end (array) \ right] = \ left [\ begin (array) (* (35) (r) ) -3 \\ 8 \\ 0 \\\ end (array) \ right] \]

Answer: $ \ left [\ begin (array) (* (35) (r)) - 3 \\ 8 \\ 0 \\\ end (array) \ right] $.

Task 6. Perform multiplication:

\ [\ left [\ begin (array) (* (35) (r)) 1 & 2 & -3 \\\ end (array) \ right] \ cdot \ left [\ begin (array) (* (35) (r)) 3 & 1 & -1 \\ 4 & -1 & 3 \\ 2 & 6 & 0 \\\ end (array) \ right] \]

Solution. Again, everything is agreed: $ \ left [1 \ times 3 \ right] \ cdot \ left [3 \ times 3 \ right] = \ left [1 \ times 3 \ right] $. We count the work:

\ [\ left [\ begin (array) (* (35) (r)) 1 & 2 & -3 \\\ end (array) \ right] \ cdot \ left [\ begin (array) (* (35) (r)) 3 & 1 & -1 \\ 4 & -1 & 3 \\ 2 & 6 & 0 \\\ end (array) \ right] = \ left [\ begin (array) (* (35) ( r)) 5 & -19 & 5 \\\ end (array) \ right] \]

Answer: $ \ left [\ begin (matrix) 5 & -19 & 5 \\\ end (matrix) \ right] $.

As you can see, when we multiply the row vector and the column vector by a square matrix, we always get a row or column of the same size in the output. This fact has many applications - from the solution linear equations to all sorts of coordinate transformations (which ultimately also come down to systems of equations, but let's not talk about the sad).

I think everything was obvious here. Let's move on to the final part of today's lesson.

Exponentiation of a matrix

Among all multiplication operations, the exponentiation deserves special attention - this is when we multiply the same object by itself several times. Matrices are no exception, they can also be raised to various degrees.

Such works are always consistent:

\\ cdot \ left [n \ times n \ right] = \ left [n \ times n \ right] \]

And they are designated in the same way as ordinary degrees:

\ [\ begin (align) & A \ cdot A = ((A) ^ (2)); \\ & A \ cdot A \ cdot A = ((A) ^ (3)); \\ & \ underbrace (A \ cdot A \ cdot \ ldots \ cdot A) _ (n) = ((A) ^ (n)). \\ \ end (align) \]

At first glance, everything is simple. Let's see how it looks in practice:

Problem 7. Raise the matrix to the indicated power:

$ ((\ left [\ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right]) ^ (3)) $

Solution. Well OK, let's build. First, let's square:

\ [\ begin (align) & ((\ left [\ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right]) ^ (2)) = \ left [\ begin (matrix ) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right] \ cdot \ left [\ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right] = \\ & = \ left [\ begin (array) (* (35) (r)) 1 \ cdot 1 + 1 \ cdot 0 & 1 \ cdot 1 + 1 \ cdot 1 \\ 0 \ cdot 1 + 1 \ cdot 0 & 0 \ cdot 1 + 1 \ cdot 1 \\\ end (array) \ right] = \\ & = \ left [\ begin (array) (* (35) (r)) 1 & 2 \\ 0 & 1 \ \\ end (array) \ right] \ end (align) \]

\ [\ begin (align) & ((\ left [\ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right]) ^ (3)) = ((\ left [\ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right]) ^ (3)) \ cdot \ left [\ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end ( matrix) \ right] = \\ & = \ left [\ begin (array) (* (35) (r)) 1 & 2 \\ 0 & 1 \\\ end (array) \ right] \ cdot \ left [ \ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right] = \\ & = \ left [\ begin (array) (* (35) (r)) 1 & 3 \\ 0 & 1 \\\ end (array) \ right] \ end (align) \]

That's all.:)

Answer: $ \ left [\ begin (matrix) 1 & 3 \\ 0 & 1 \\\ end (matrix) \ right] $.

Problem 8. Raise the matrix to the indicated power:

\ [((\ left [\ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right]) ^ (10)) \]

Solution. Just don't cry now about the fact that "the degree is too great", "the world is not just" and "the teachers have completely lost their shores." In fact, everything is easy:

\ [\ begin (align) & ((\ left [\ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right]) ^ (10)) = ((\ left [\ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right]) ^ (3)) \ cdot ((\ left [\ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right]) ^ (3)) \ cdot ((\ left [\ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right]) ^ (3)) \ cdot \ left [\ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right] = \\ & = \ left (\ left [\ begin (matrix) 1 & 3 \\ 0 & 1 \\\ end (matrix) \ right] \ cdot \ left [\ begin (matrix) 1 & 3 \\ 0 & 1 \\\ end (matrix) \ right] \ right) \ cdot \ left (\ left [ \ begin (matrix) 1 & 3 \\ 0 & 1 \\\ end (matrix) \ right] \ cdot \ left [\ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right ] \ right) = \\ & = \ left [\ begin (matrix) 1 & 6 \\ 0 & 1 \\\ end (matrix) \ right] \ cdot \ left [\ begin (matrix) 1 & 4 \\ 0 & 1 \\\ end (matrix) \ right] = \\ & = \ left [\ begin (matrix) 1 & 10 \\ 0 & 1 \\\ end (matrix) \ right] \ end (align) \ ]

Note that in the second line we used associativity multiplication. Actually, we used it in the previous task, but there it was implicit.

Answer: $ \ left [\ begin (matrix) 1 & 10 \\ 0 & 1 \\\ end (matrix) \ right] $.

As you can see, there is nothing difficult in raising a matrix to a power. The last example can be summarized:

\ [((\ left [\ begin (matrix) 1 & 1 \\ 0 & 1 \\\ end (matrix) \ right]) ^ (n)) = \ left [\ begin (array) (* (35) (r)) 1 & n \\ 0 & 1 \\\ end (array) \ right] \]

This fact is easy to prove through mathematical induction or direct multiplication. However, it is far from always possible to catch such patterns when raising to a power. Therefore, be careful: it is often easier and faster to multiply several matrices “straight ahead” than to look for some regularities there.

In general, do not look for the highest meaning where it does not exist. In conclusion, consider raising to a power of a larger matrix - as much as $ \ left [3 \ times 3 \ right] $.

Problem 9. Raise the matrix to the indicated power:

\ [((\ left [\ begin (matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\ end (matrix) \ right]) ^ (3)) \]

Solution. Let's not look for patterns. We work hard:

\ [((\ left [\ begin (matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\ end (matrix) \ right]) ^ (3)) = (( \ left [\ begin (matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\ end (matrix) \ right]) ^ (2)) \ cdot \ left [\ begin (matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\ end (matrix) \ right] \]

First, let's square this matrix:

\ [\ begin (align) & ((\ left [\ begin (matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\ end (matrix) \ right]) ^ ( 2)) = \ left [\ begin (matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\ end (matrix) \ right] \ cdot \ left [\ begin (matrix ) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\ end (matrix) \ right] = \\ & = \ left [\ begin (array) (* (35) (r )) 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\\ end (array) \ right] \ end (align) \]

Now let's cube:

\ [\ begin (align) & ((\ left [\ begin (matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\ end (matrix) \ right]) ^ ( 3)) = \ left [\ begin (array) (* (35) (r)) 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\\ end (array) \ right] \ cdot \ left [\ begin (matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\ end (matrix) \ right] = \\ & = \ left [\ begin ( array) (* (35) (r)) 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\ end (array) \ right] \ end (align) \]

That's all. The problem has been solved.

Answer: $ \ left [\ begin (matrix) 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\ end (matrix) \ right] $.

As you can see, the amount of calculations has increased, but the meaning has not changed at all. :)

This lesson can be finished. Next time we will consider the inverse operation: we will search for the original factors using the existing product.

As you probably already guessed, we will talk about inverse matrix and methods of finding it.

Lecture 6. Parallel numerical algorithms for solving typical problems of computational mathematics: matrix multiplication.

Matrix-vector multiplication. Achieving the fastest possible performance. Using middle-level parallelism. Organization of parallel computations for p = n. Using a limited set of processors. Matrix multiplication. Macro-operational analysis of algorithms for solving problems. Organization of parallelism based on data sharing.

Matrix-vector multiplication

The problem of multiplying a matrix by a vector is determined by the relations

Thus, obtaining the resulting vector involves repeating the same type of operations for multiplying the rows of the matrix and the vector. Obtaining each such operation includes element-wise multiplication of the elements of the matrix row and the vector and the subsequent summation of the resulting products. The total number of required scalar operations is estimated as

As follows from the actions performed when multiplying a matrix and a vector, parallel methods for solving the problem can be obtained on the basis of parallel summation algorithms (see Section 4.1). In this section, the analysis of parallelization methods will be supplemented by a consideration of the organization of parallel computations depending on the number of processors available for use. In addition, using the example of the problem of multiplying a matrix by a vector, attention will be drawn to the need to select the most appropriate topology of a computing system (existing communication channels between processors) to reduce costs for organizing interprocessor communication.

Achieving the fastest possible performance ()

Let's analyze information dependencies in the matrix-vector multiplication algorithm for choosing possible ways parallelization. As you can see, the operations of multiplying individual rows of the matrix by a vector performed during the calculations are independent and can be performed in parallel;

The multiplication of each row by a vector involves independent element-wise multiplication and can also be performed in parallel;

The summation of the resulting products in each operation of multiplying a row of a matrix by a vector can be performed according to one of the previously considered variants of the summation algorithm (sequential algorithm, conventional and modified cascade circuits).

Thus, the maximum required number of processors is determined by the value

The use of such a number of processors can be represented as follows. Many processors are divided into groups

each of which represents a set of processors for performing the operation of multiplying an individual row of a matrix by a vector. At the beginning of computations, an element of the matrix row and the corresponding element of the vector are sent to each processor of the group. Next, each processor performs a multiplication operation. Subsequent calculations are performed according to the cascade summation scheme. For illustration in fig. 6.1 shows the computational scheme for the processors of the group with the dimension of the matrix.

Rice. 6.1. Computational scheme of the operation of multiplying a row of a matrix by a vector

The execution time of a parallel algorithm when using processors is determined by the execution time of the parallel multiplication operation and the execution time of the concatenated circuit

As a result, the performance indicators of the algorithm are determined by the following ratios:

For the considered problem of matrix-vector multiplication, the most suitable topologies are structures in which fast transfer data (paths of unit length) in a cascade summation scheme (see Fig. 4.5). Such topologies are a structure with a complete system of links ( complete graph) and hypercube... Other topologies lead to an increase in communication time due to lengthening of data transmission routes. So, in the linear ordering of processors with a system of connections only with the nearest neighbors to the left and to the right ( ruler or ring) for a cascade scheme, the length of the transmission path of each received partial sum at iteration,, is equal. If we assume that data transmission along a length route in topologies with a linear structure requires data transmission operations, the total number of parallel operations (total path length) of data transmission is determined by the value

(excluding data transfers for bootstrapping processors).

Application of a computing system with a rectangular topology two-dimensional lattice size leads to a simple and clear interpretation of the calculations performed (the network structure corresponds to the structure of the processed data). For such a topology, it is most expedient to place the matrix rows along the horizontal lines of the lattice; in this case, the elements of the vector must be sent along the verticals of the computing system. Computations with this arrangement of data can be performed in parallel along the lattice lines; as a result, the total number of data transfers matches the results for the ruler ().

The communication actions performed when solving the assigned task consist in transferring data between pairs of MCS processors. Detailed analysis the duration of the implementation of such operations is carried out in p. 3.3.

4. Recommendations for the implementation of the parallel algorithm... When implementing a parallel algorithm, it is advisable to select the initial stage of loading the processors used with initial data. The simplest such initialization is provided for the topology of a computing system with a topology in the form complete graph(loading is provided using one parallel data transfer operation). When organizing a plurality of processors in the form hypercube it may be useful to have two-level control of the boot process, in which the central control processor sends the matrix and vector rows to the control processors of the processor groups, which, in turn, send the elements of the matrix and vector rows to the executive processors. For topologies in the form rulers or rings sequential data transfer operations are required with a sequentially decreasing amount of data transferred from to elements.

Using middle-level parallelism ()

1. Choosing a parallel computation method... With a decrease in the available number of processors used (), the usual cascade summation scheme when performing multiplication of matrix rows by a vector becomes inapplicable. For simplicity of presentation of the material, we put and use a modified cascade circuit. In this case, the initial load of each processor increases and the processor is loaded () with parts of the matrix and vector rows. The execution time of the operation of multiplying a matrix by a vector can be estimated as the value

When using the number of processors required to implement the modified cascade circuit, i.e. at , this expression gives an estimate of the runtime (at ).

With the number of processors, when the execution time of the algorithm is estimated as, a new scheme for parallel execution of computations can be proposed, in which for each iteration of the cascade summation non-overlapping processor sets... With this approach, the available number of processors turns out to be sufficient to implement only one operation of multiplying a row of a matrix and a vector. In addition, when performing the next iteration of the cascade summation, the processors responsible for the execution of all previous iterations are free. However, this disadvantage of the proposed approach can be turned into an advantage by using idle processors to process the next rows of the matrix. As a result, the following scheme can be formed conveyor performing matrix and vector multiplication:

The set of processors is divided into non-overlapping processor groups

the group,, consists of processors and is used to iterate the cascade algorithm (the group is used to implement elementwise multiplication); the total number of processors;

Initialization of calculations consists in element-by-element loading of the processors of the group with the values of 1 row of the matrix and the vector; after the initial loading, a parallel operation of element-wise multiplication is performed and the subsequent implementation of a conventional cascaded summation circuit;

When performing calculations, each time after the completion of the operation of elementwise multiplication, the processors of the group are loaded with the elements of the next row of the matrix and the computation process for the newly loaded data is initiated.

As a result of applying the described algorithm, many processors implement a pipeline for performing the operation of multiplying a matrix row by a vector. On such a conveyor, there can be several separate rows of the matrix at the same time at different stages of processing. So, for example, after element-wise multiplication of the elements of the first row and vector, the processors of the group will perform the first iteration of the cascade algorithm for the first row of the matrix, and the processors of the group will perform element-wise multiplication of the values of the second row of the matrix, etc. For illustration in fig. 6.2 shows the situation of the computation process after 2 iterations of the pipeline for.

Rice. 6.2. The state of the pipeline for the operation of multiplying a matrix row by a vector after performing 2 iterations

2. Evaluation of performance indicators of the algorithm... The multiplication of the first row by a vector in accordance with the cascade scheme will be completed, as usual, after performing () parallel operations. For other lines, in accordance with the pipeline scheme for organizing calculations, the appearance of the results of multiplication of each successive line will occur after the completion of each subsequent iteration of the pipeline. As a result, the total execution time of the matrix-vector multiplication operation can be expressed as

This estimate is somewhat larger than the execution time of the parallel algorithm described in the previous paragraph (), however, the newly proposed method requires less data to be transmitted (the vector is sent only once). In addition, the use of a pipelined scheme leads to an earlier appearance of a part of the calculation results (which can be useful in a number of data processing situations).

As a result, the performance indicators of the algorithm are determined by the following ratios:

3. Choice of the topology of the computing system... The expedient topology of a computing system is completely determined by the computing scheme - this is a complete binary tree height. The number of data transfers in this network topology is determined by the total number of iterations performed by the pipeline, i.e.

Initialization of calculations begins with the leaves of the tree, the results of the summation are accumulated in the root processor.

The analysis of the complexity of the performed communication actions for computing systems with other topologies of interprocessor connections is supposed to be carried out as self-assignment(see also section 3.4).

Organization of parallel computing when

1. Choosing a parallel computation method... When using processors for multiplying a matrix by a vector, the parallel algorithm of row-by-row multiplication, previously discussed in the manual, can be used, in which the rows of the matrix are distributed among the processors row by row and each processor implements the operation of multiplying any single row of the matrix by a vector. Another possible way to organize parallel computations could be to build a pipeline circuit for the operation of multiplying a matrix row by a vector(dot product of vectors) by arranging all available processors in the form of a linear sequence ( rulers).

A similar calculation scheme can be defined as follows. We represent the set of processors in the form of a linear sequence (see Fig. 4.7):

each processor,,, is used to multiply the elements of a matrix column and a vector element. Performing calculations on each processor,, is as follows:

The next element of the matrix column is requested;

The elements and are multiplied;

The result of the computation of the previous processor is requested;

Addition of values is performed;

The resulting result is sent to the next processor.

Rice. 6.3. The state of the linear pipeline for the operation of multiplying a matrix row by a vector after performing two iterations

When initializing the described scheme, it is necessary to perform a number of additional steps:

During the first iteration, each processor additionally requests a vector element;

To synchronize computations (during the next iteration of the circuit, the computation result of the previous processor is requested) at the initialization stage, the processor,, executes () a wait cycle.

In addition, for the homogeneity of the described scheme for the first processor, which does not have a previous processor, it is advisable to introduce an empty addition operation ( ).

For illustration in fig. 6.3 shows the state of the computation process after the second iteration of the pipeline at.

2. Evaluation of performance indicators of the algorithm... The multiplication of the first row by a vector in accordance with the described pipeline scheme will be completed after performing () parallel operations. The result of the multiplication of the following lines will occur after the completion of each next iteration of the pipeline (recall that the iteration of each processor includes the execution of multiplication and addition operations). As a result, the total execution time of the matrix-vector multiplication operation can be expressed as:

This score is also greater than the minimum possible time execution of a parallel algorithm for. The usefulness of using a pipelined computational scheme is, as noted in the previous paragraph, in reducing the amount of transmitted data and in the earlier appearance of a part of the computational results.

The performance indicators of this computational scheme are determined by the ratios:

, ,

3. Choice of the topology of the computing system... The necessary topology of the computing system for executing the described algorithm is uniquely determined by the proposed computing scheme - this is a linearly ordered set of processors ( ruler).

Using a limited set of processors ()

1. Choosing a parallel computation method... When the number of processors is reduced to a value, a parallel computational scheme for multiplying a matrix by a vector can be obtained as a result of adapting the row-by-row multiplication algorithm. In this case, the cascade circuit for summing the results of element-wise multiplication degenerates and the operation of multiplying a matrix row by a vector is completely performed on a single processor. The computational scheme obtained with this approach can be concretized as follows:

A vector and matrix rows are sent to each of the available processors;

The operation of matrix-vector row multiplication is performed using the usual sequential algorithm.

It should be noted that the size of the matrix may not be a multiple of the number of processors, and then the rows of the matrix cannot be divided equally between the processors. In these situations, it is possible to deviate from the requirement for uniformity of the processor load and, to obtain a simpler computational scheme, accept the rule that data placement on processors is carried out only row by row (i.e., the elements of one row of the matrix cannot be shared between several processors). Unequal number of lines leads to different computational load of processors; thus, the completion of computations (the total duration of solving the problem) will be determined by the operating time of the most loaded processor (in this case, part of this total time, individual processors may be idle due to the exhaustion of their share of computations). Uneven loading of processors reduces the efficiency of using the MCS and, as a result of consideration this example we can conclude that balancing problem

3. Choice of the topology of the computing system... In accordance with the nature of the interprocessor interactions performed in the proposed computational scheme, the organization of processors in the form stars(see fig. 1.1). A control processor of a similar topology can be used to load the computational processors with initial data and to receive the results of the performed computations.

Matrix multiplication

The problem of multiplying a matrix by a matrix is determined by the relations

(for simplicity of presentation, we will assume that the multiplied matrices and are square and have order).

The analysis of possible ways of parallel execution of this task can be carried out by analogy with the consideration of the problem of matrix-vector multiplication. Leaving a similar analysis for self-study, we will show, using the example of the matrix multiplication problem, the use of several general approaches that make it possible to form parallel methods for solving complex problems.