Help: Systolic arrays and matrix multiplication

February 11, 2010 By

Commenter apit had given me a problem which I am unable to help with: Matrix multiplication using systolic arrays.

I searched and I came up with very little. About the only thing I understood was that the “array” was not the variable array in code. It’s an array of processors. Systolic arrays are used for parallel processing.

So how is it used for matrix multiplication?

Hmm… I’ve never heard of systolic arrays before this. So I asked my friend and he found a PowerPoint presentation that gave the best explanation that I could understand.

Systolic arrays & their applications, by Jonathan Break.

I believe apit didn’t understand that each “array cell” don’t have past memory of operations, only an intermediate result.

If you happen to understand it, and can explain it better than I do, please chime in with your comment. Thanks.

Filed Under: Programming Tagged With: , , , , ,

Answer for matrix applications and civil engineering question

December 10, 2009 By

My friend, Christopher Ng (who has an electrical engineering degree, is currently an IT project manager, and is also a finance author. Talk about polymathy…) has generously helped me answer that matrix applications and civil engineering question. Let me bring it up again:

How do you picture matrix least-squares method of a traverse adjustment in surveying and in strain-stress material? Tell me about diagonal matrix practical interpretation.

I read through his answer and frankly speaking, and I’m ashamed to say, I don’t quite understand it.

He gave this link first:
http://answers.yahoo.com/question/index?qid=20091207151537AAYSibI

Then

Surveys and stress-strain characteristics are two different application domains in civil engineering. I can shed some light on matrices, MLS and stress-strain diagrams.

If you wiki the least squares approach approach [sic], you can find that the generalized problem can be expressed as some sort of a matrix. Solving matrix via quadratic minimization obtains the solution to the least squares problem. Bx = y

If you wiki stress-strain characteristics, it’s simple the physics we used to learn called Hooke’s law. A graph that plots force on the x axis and extension on the y-axis. The least squares approach is just like we do in O level physics, we draw the most probable line that crosses the origin point.

So the picture is that each plot (x,y) can be placed on the matrix and the aim is to draw a line through the points to determine Youngs modulus.

He then went on to explain

The traverse survey occurs when civil engineers take complicated compasses and walk the perimeter of a construction site. They enter the coordinates in bearings and distances traveled into a CAD software system. Ultimately, these engineers are expected to walk to the starting point and trace some kind of loop which is then translated into a map.

The MLS is used to correct errors and adjust the x,y coordinates in a map as there are 3D effects in terrain.

I have no idea how MLS works in this case but you can seek Crandall’s method in your web search to look for graphical examples.

MLS refers to matrix least squares. And O level physics is a physics examination taken by Singaporean students typically at age 16 for entrance towards higher education.

And yeah, what my friend said.

Filed Under: Curiosita Tagged With: , , ,

Help – Matrix applications and civil engineering

December 7, 2009 By

I have a problem. One of my readers asked me a question and I don’t have an answer. The question (paraphrased and mangled slightly) is:

How do you picture matrix least-squares method of a traverse adjustment in surveying and in strain-stress material? Tell me about diagonal matrix practical interpretation.

I think my brain exploded after reading it. What in tarnation is a traverse adjustment? Holy smokes, strain-stress material? I have no idea what I was in for…

After weeks of sitting on it, and doing some preliminary research, I’ve decided I can’t answer it. I’m sorry I let you down, O reader who sent me the question. I presume this is related to civil engineering. I know little about it, and I’ll probably spout rubbish if I start answering.

This is where you come in. Help answer the question. You can write it in a comment, or contact me via email. A civil engineering reader gets help, and you get a warm fuzzy feeling of doing something good.

UPDATE: We have an answer.

Filed Under: Curiosita Tagged With: , , ,

Our future – The Sims and The Matrix

June 15, 2009 By

I was wondering, what would happen if we run out of resources on Earth? We’d probably all die, which is kind of depressing. So I thought of how not to run out of resources in the first place.

Earth plant
[image by Andrejs Zemdega]

I have 2 obvious answers. One is regeneration of our resources, through recycling, reusing and reducing. That doesn’t appear to be enough, since we consume too much.

The second answer is intergalactic colonisation. “We can’t control our own planet’s resources, so we’ll just take over another planet!” Even if we disregard the moral and selfish motivation of that reason, there’s still one tiny problem. Our scientific space program isn’t up to par yet. We might run out of resources before our science and technology is advanced enough.

So I came up with another answer. Now, if you assume that humans are driven by needs and wants, then… ok, let me define needs and wants first. Needs are critical to human survival, or at least make it easier to survive. Wants are wishes… let me give examples then. You need food, shelter and clothing (to protect from weather). You want to travel, to play video games and to wear Gucci products.

The distinction between a need and want is subjective (does steak qualify as a need or want?). We don’t need the distinction to be obvious anyway. So what’s the answer? Push the wants into a virtual world.

Create a virtual world where the wants can be satisfied by bits and bytes rather than carbon, wool, oil, water and other natural resources.

For it to work, the experience must be indistinguishable from what can be experienced now. Hence The Matrix. What we call reality, is just a sum total of what our senses tell us anyway. Simulate the senses correctly, and you get “reality”. The game franchise “The Sims” has been steadily heading towards this end. Its limits are the number of objects available (including other Sims), the number of interactions available and the number of sensory inputs.

With the wants satisfied in the virtual world, there should be more resources in the real world. If nothing else, this should give the option of regeneration more time to regenerate resources. Or more time to spread our human genes to other galaxies.

Is the virtual world solution easier to implement (we programmers have much to do then)? Will it upset the economy (most definitely)? Will the virtual world consume more resources (servers have carbon footprints too)?

Filed Under: Curiosita Tagged With: , , , ,

Matrices for programmers

August 11, 2008 By

Following the fine tradition of the colour theory post, you are getting another crash course. This time, a lesson in matrices. You’re going to be fine. And yes, I’ll hold your hand while you do this. *smile*

For those who are mathematically inclined, we’ll be working in the realm of real numbers (which I talked about briefly when discussing floating points). Let’s start with…

Scalars

Scalars are simply numbers. For example, 2 is a scalar. So is 3.14159 and 1.618. And so is -273.15. Bonus points if you can figure out what those numbers are special for.

Scalars are stored as normal variables in code. Your ints, floats, doubles come in handy.

Scalars are typically denoted by a lowercase alphabet, such as a or b or c.

Vectors

Vectors are series of scalars. For example, [1 3 5 7 9] is a vector.

You typically store vectors as an array. For example,

int[] v = new int[] { 1, 3, 5, 7, 9 };

Vectors are typically denoted by a lowercase alphabet in bold, such as v.

Matrices

Matrices are series of series of scalars, or series of vectors. In code, they are typically stored as an array of arrays.

int[,] A = new int[3, 3];

3 by 3 matrix

Matrices are also known as multidimensional arrays. The dimension of a matrix is m-by-n, where m is the number of rows and n is the number of columns.

When either m or n is 1, we get a vector. So a vector is a special case of a matrix. And because of this, we have to define…

Row and column vectors

It’s easier to just show you how they look like.

Row and column vectors

A row vector is a matrix where the number of rows is 1. A column vector is a matrix where the number of columns is 1. While we’re at it, a scalar can be thought of as a matrix where the number of rows and columns are both 1.

For our purposes of working towards 3D programming, we’ll be focusing on the column vector. It doesn’t matter which one we use when coding, but in terms of notation, we’ll be using column vectors. You will see why later on.

Matrix entries

Individual entries are referred to with the notation A[i,j] (or ai,j) where A is the matrix, i is the i-th row and j is the j-th column. Typically, we have
1 <= i <= m and 1 <= j <= n, where m is the number of rows and n is the number of columns.

Take note, because you'll be using them in code. So know how your programming language does indices of arrays. If your language starts with the 0-th element, make sure to shift positions by one less. Then you have
0 <= i <= m-1 and 0 <= j <= n-1.

The 0 index has tripped many a programmer, so be careful.

Square matrices

This is a special case where both the number of rows and number of columns are equal. For example, a 3 by 3 matrix, or a 4 by 4 matrix.

In a stroke of coincidence, we will also be focusing on 3 by 3 and 4 by 4 matrices. Hint: It’s because we’re working in 3D.

Identity matrix

In math, there is a number such that when you multiply anything by it, you get back the same thing. It’s the number 1. For example, 8 * 1 = 1 * 8 = 8.

We have the same concept for matrices. There is a matrix such that when you multiply any matrix by it, you get the same original matrix back. It’s called the identity matrix, typically denoted by an uppercase “I”.

Identity matrix

We’ll look at matrix operations soon.

Zero matrix

You know that multiplication unity described above when defining the identity matrix? Guess what, there’s a number such that when you add anything to it, you get back the same thing. It’s the number 0. For example, 8 + 0 = 0 + 8 = 8.

Similarly, we have the zero matrix. It’s simply a matrix with zeroes in all its entries. It’s denoted by a big gigantic 0. Probably not quite useful to you, but nevertheless, you now know something more.

Symmetrical matrices

Symmetrical matrices are symmetrical about the diagonal. Where’s the diagonal? Look at this:

Matrix diagonal

For a 3 by 3 matrix with values:
a b c
d e f
g h i

Entries a, e and i form the diagonal. Notation wise, A[i,i] are the diagonal entries.

If a matrix has zeroes in entries below the diagonal, it’s known as an upper triangular matrix. In our case, d = g = h = 0.

Similarly, if a matrix has zeroes in entries above the diagonal, it’s known as a lower triangular matrix. In our case, b = c = f = 0.

What symmetry means in this case is b=d, c=g and f=h. The general formula is
A[i,j] = A[j,i]

To speed up computations when checking symmetry, some algorithms use
A[i,j] = A[j,i], where i < j

The extra condition leaves out the diagonal and entries below the diagonal. No point double checking values, right?

Transpose of a matrix

Now that we know what a symmetrical matrix and its diagonal, we can define the transpose of a matrix. What you do is simply flip the matrix about its diagonal.

For a matrix A whose values are:
a b c
d e f
g h i

Its transpose is:
a d g
b e h
c f i

The transpose of a matrix A is denoted by AT. So if A = AT, A is a symmetrical matrix.

Yes, we’re dealing with square matrices. Rectangular matrices aren’t useful for our purposes in 3D programming, and you’re welcome to research on its practical uses (try “operations research“).

The inverse of a matrix

The inverse of a square matrix A is denoted by A-1, where
AA-1 = A-1A = I

Yes, I know I still haven’t covered matrix multiplication. Just go with it a little longer…

For a matrix product AB, it’s inverse is
(AB)-1 = B-1A-1

Then this looks beautiful:
(AB)-1AB
= B-1A-1AB
= B-1IB
= B-1B
= I

Don’t you think that looks beautiful? *smile*

Matrix equality

Matrices A and B are said to be equal if every corresponding entry of both matrices are equal. In notation, A[i,j] = B[i,j] for all i and j.

Matrix addition (and subtraction)

A matrix C is said to be the sum of matrices A and B if
C[i,j] = A[i,j] + B[i,j] for all i and j.

Subtraction is similar. Let me show you a scalar example.
8 – 5 = 8 + (-5)
Same thing for matrices. The negative sign is “pushed in” to individual entries.

Matrix multiplication by scalar

Let’s multiply matrices by scalars first. It’s easy.

Scalar matrix multiplication

Just multiply the scalar with all the entries in the matrix.

Matrix multiplication by vector

This one’s a little more complicated. For our purposes, we are concerned with multiplying a matrix A by a column vector v. Yes, the order and the type of vector matters. Let’s look at a diagram.

Matrix vector multiplication

The result is a column vector. Suppose we multiply matrix A by column vector x and we get a column vector y, the general formula is
y[i] = A[i,0] * x[0] + A[i,1] * x[1] + … + A[i,n] * x[n]

It actually looks much more concise if I can use the summation notation… BUT, I’m trying to simplify things for you. Hopefully, you can visualise how it works with the diagram. I’ll write another post with code to explain this.

You can’t multiply a matrix by a row vector though. Hopefully through the diagram, you’ll see why it doesn’t work. What happens is, you multiply each row of the matrix by the values down the column vector. Since a row vector only has one value “down the column”, it doesn’t make sense to multiply matrices by row vectors.

You can multiply a row vector by a matrix to get a row vector. But it’s not useful for our purposes. If you understand a little about 3D transformations, then A is a transformation matrix, and x is a vertex. For example, A could be a translation matrix and moves x to point y. If you don’t understand any of this, relax, we’ll get there together soon.

Matrix and matrix multiplication

This is complicated to show and explain, but once you get the idea, it’s actually easy to code.

Matrix by matrix multiplication

I’ll leave it to you to figure out the general formula… It’s similar to the one with matrix by vector multiplication, only with more vectors. *smile* This is what I do in university, write out a’s and subscripts, and summation notations in my lecture notes and tutorial questions…

I’ll write another post explaining this (together with the matrix by vector multiplication) with code to illustrate the use.

In terms of 3D transformations, you could have a bunch of transformations done, say you rotate something, then translate (move) it. So you have something like TRx, where R is the rotation matrix, T is the translation matrix and x is the vertex.

Note the order. The earlier (in order) a transformation is done, the closer it is to the vertex in question. Basically you reverse the order of transformations when implementing.

Since we’re at it, matrix multiplications are not commutative. What it means is that
AB != BA
The order is important.

As an exercise, visualise the difference between moving something then rotate, and rotate then move.

End of crash course

Whew… *wipe sweat* How’re you doing? Still with me?

Good. This sets the foundation you need for understanding 3D programming. Yay! Review what you’ve read, do some research if needed, and I’ll see you next time.

Filed Under: Mathematics Tagged With: , , , , ,