# Matrix Operations I

1 Matrix operations

There are three basic matrix ope rations that would be part of any GPU
matrix toolkit:

1. The inner product of two vectors c = a · b.

2. Matrix-vector operations: y = Ax.

3. Matrix-Matrix operations: C = A + B, D = AB, E = A−1.

A number of problems can be solved once one has these basic operations
(especially in physical simulations). This is one of the most studied problems
on the GPU.

2 The Inner Product

Consider the inner product c = a · b, which we rewrite as

2.1 Technique 1: Small memory

Each vector is stored in a 1D texture. In the ith rendering pass, we render a
single point at coordinates (0,0), having a single texture coordinate i . The
fragment program uses i to index into the two textures and returns the value
, where s is the running sum maintained over the previous i − 1
passes. Note that since we cannot read and write the location where s is
stored in a single pass, we use a ping-pong trick to maintain s.

This procedure takes n passes, and requires only a fixed number of texture
locations (excluding the storage for a and b).

2.2 Technique 2: Fewer passes

The second technique uses more working memory (n units), but requires
fewer passes. We write a and b as 2D textures (2D textures al low for more
storage
, since the dimension of a texture is typically bounded, and are better
optimized by the rasterizer).

We now multiply the contents of the textures, storing the result in a
third texture c. This can be done with a simple fragment program that takes
the fragment coordinates and looks up the a and b textures, returning their
product. We render a single quad in order to activate the fragment program.

Finally, all the numbers in c must be summed together. This can be done
in log n passes , using a standard reduce operation .

This procedure takes only log n passes, but requires 3n units of texture
memory.

3 Matrix-Matrix operations

We can store matrices as 2D textures. Addition is trivial .

3.1 Multiplication

3.2 Technique 1: The Basic Approach

”Fast matrix multiplies using graphics hardware ” by Larsen and
McAllister”

Express multiplication of two matrices as dot product of vectors of matrix
rows and columns. That is to compute some cell cij of matrix C, we take the
dot product of row i of matrix A with column j of matrix B:

1st program used multitexturing and blending, each plane would compute
each place in the answer. In 1st pass: AB :

We can use inner quad idea to do this:

pass 1
if at location (x, y)
output
pass 2

output
pass k
output

1)uses n passes
2)space N = n2

3.3 Technique 2: A Speedup

”Dense Matrix Multiplication” by
To make it faster:
Instead of making one computation per pass, compute multiple additions per
pass in fragment program:

Pass 1 becomes: output
Must consider that there is a tradeoff between the length of fragment
program vs. the number of passes.

3.4 Technique 3: Using All Channels

”Cache and Bandwidth Aware Matrix Multiplication on the GPU”,
by Hall, Carr and Hart”.

We have been using only the red component, propose storing across all
colors:

divide into 2:

Basically a swizzle operation to speed things up.
Closing thought: The basic idea here is using the inner product calculation
in parellel.

 Prev Next

Start solving your Algebra Problems in next 5 minutes!

 Algebra Helper Download (and optional CD) Only \$39.99 Click to Buy Now: OR
2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of May 25th you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:

Step 2 : Let Algebra Helper solve it:

Step 3 : Ask for an explanation for the steps you don't understand:

Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!

 Algebra Helper Download (and optional CD) Only \$39.99 Click to Buy Now: OR
2Checkout.com is an authorized reseller
of goods provided by Sofmath

 "It really helped me with my homework.  I was stuck on some problems and your software walked me step by step through the process..." C. Sievert, KY

 Sofmath 19179 Blanco #105-234San Antonio, TX 78258 Phone: (512) 788-5675Fax: (512) 519-1805
 Home   : :   Features   : :   Demo   : :   FAQ   : :   Order Copyright © 2004-2018, Algebra-Answer.Com.  All rights reserved.