-
-
Notifications
You must be signed in to change notification settings - Fork 436
Expand file tree
/
Copy path5-17-MatrixEfficiencyInHardware.pg
More file actions
126 lines (83 loc) · 5.38 KB
/
5-17-MatrixEfficiencyInHardware.pg
File metadata and controls
126 lines (83 loc) · 5.38 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
## DESCRIPTION
## On the efficiency of combinint transformation matrices in computer applications
## ENDDESCRIPTION
## DBsubject(Linear Algebra)
## DBchapter(Linear Transformations)
## DBsection(Associated matrices)
## Date(02/02/2018)
## Institution(Bentley University)
## Author(Nathan Carter)
## TitleText1('Introduction to the Mathematics of Computer Graphics')
## AuthorText1('Nathan Carter')
## EditionText1('1')
## Section1('5')
## Problem1('17')
## KEYWORDS('transformations','matrices','matrix multiplication')
DOCUMENT();
loadMacros(
"PGstandard.pl",
"MathObjects.pl",
"PGML.pl",
"PGcourse.pl",
);
Context("Matrix");
$showPartialCorrectAnswers = 1;
$nmats = random(7,10);
$npts = random(2000,10000,1000);
$ans1 = ($nmats-1)*112 + 28;
$ans2 = $ans1 * $npts;
$ans3 = 28*$nmats;
$ans4 = $ans3 * $npts;
$ans5 = ($nmats-1)*112 + 28*$npts;
TEXT(beginproblem());
BEGIN_PGML
Suppose a computer program needs to apply an affine transformation to a complex three-dimensional object made up of [$npts] points. The transformation is composed of [$nmats] matrices (call them [`M_1`] through [`M_{[$nmats]}`]), so for each point [`(x, y, z)`] in the object, the following operation is performed.
[`
\left[\begin{array}{c} ~ \\ ~ M_1 ~ \\ ~ \end{array}\right] ~
\left[\begin{array}{c} ~ \\ ~ M_2 ~ \\ ~ \end{array}\right] ~
\left[\begin{array}{c} ~ \\ ~ M_3 ~ \\ ~ \end{array}\right] ~
\cdots
\left[\begin{array}{c} ~ \\ ~ M_{[$nmats-1]} ~ \\ ~ \end{array}\right] ~
\left[\begin{array}{c} ~ \\ ~ M_{[$nmats]} ~ \\ ~ \end{array}\right] ~
\left[\begin{array}{c} x \\ y \\ z \\ 1 \end{array}\right]
`]
Each multiplication of a matrix times a column vector involves 16 multiplications (of one number by another) and 12 additions, for a total of 28 arithmetic operations. Each multiplication of a matrix times another matrix involves 64 multiplications and 48 additions, for a total of 112 arithmetic operations. (These numbers are not made up or chosen randomly; they are facts about [`4\times 4`] matrix multiplication.)
-----
The most inefficient way of applying the transformation to the [$npts] points would be to begin on the left, multiplying [`M_1`] by [`M_2`], then that result by [`M_3`], and so on along the list from left to right, and doing the same [$nmats] multiplications again for each of the [$npts] points. How many arithmetic operations would this require for transforming one point?
Answer: [_____]{$ans1}
How many would it require in total for transforming all [$npts] points?
Answer: [_____]{$ans2}
-----
A more efficient method would be to start on the right, first multiplying [`M_{[$nmats]}`] by the column vector, then multiplying [`M_{[$nmats-1]}`] by that result, and so on, proceeding along the list from right to
left.
How many arithmetic operations would this require for transforming one point?
Answer: [_____]{$ans3}
How many would it require in total for transforming all [$npts] points?
Answer: [_____]{$ans4}
Using this method would therefore save what percentage of the time of the previous method?
Answer: [_____]{(1-$ans4/$ans2)*100}%
-----
The most efficient method would be to multiply the [$nmats] matrices together and call that result [`A`] (without yet multiplying [`A`] by any column vector). After computing [`A`] (just once of course), multiply [`A`] by each of the [$npts] points, each represented as a column vector.
How many arithmetic operations would it take to compute [`A`]?
Answer: [_____]{$nmats*112-112}
How many arithmetic operations would it require to multiply [`A`] by one point?
Answer: [_____]{28}
How many would this method require in total?
Answer: [_____]{$ans5}
Using this method would therefore save what percentage of the time of the previous method?
Answer: [_____]{100*(1-$ans5/$ans4)}%
END_PGML
BEGIN_PGML_SOLUTION
To transform one point the inefficient way requires [`[$nmats-1]\times 112=[$nmats*112-112]`] for the [$nmats-1] matrix multiplications, plus another 28 for the final matrix-by-column-vector multiplication, for a total of [$ans1].
To transform [$npts] the inefficient way is that previous answer times [$npts], which is [$ans2].
-----
If we proceed from right to left instead, then each multiplication is a matrix-times-column-vector multiplication, and thus requires only 28 operations. Since there are [$nmats] matrices, it takes [`[$nmats]\times 28=[$ans3]`] operations to transform one point.
To transform all [$npts] points, it requires [`[$ans3]\times [$npts]=[$ans4]`] operations.
To see the time percentage of this method compared to the previous, we divide [`\frac{[$ans4]}{[$ans2]}=[$ans4/$ans2]`], which is [$ans4*100/$ans2]%, for a savings of [$ans4*-100/$ans2+100]%.
-----
Multiplying the [$nmats] matrices together involves only [$nmats-1] multiplications, each of which takes 112 operations. So the total number of operations to compute [`A`] is [`[$nmats-1]\times 112=[$nmats*112-112]`].
To apply [`A`] to a single point takes 28 operations, as the problem states.
To apply [`A`] to all [$npts] points takes [`28\times [$npts]=[$npts*28]`] operations, to which we add the [$nmats*112-112] operations we needed to compute [`A`], making the total number of operations in this method equal to [`[$npts*28]+[$nmats*112-112]=[$ans5]`].
To see the time percentage of this method compared to the previous, we divide [`\frac{[$ans5]}{[$ans4]}=[$ans5/$ans4]`], which is [$ans5*100/$ans4]%, for a savings of [$ans5*-100/$ans4+100]%.
END_PGML_SOLUTION
ENDDOCUMENT();