Prev: Help with Matlab hw!
Next: invert a large number of matrices
From: Val Schmidt on 21 Apr 2010 15:02
Hi everyone,
I need some ideas on how to speed up some code that appears to be memory bound. I'm only guessing that it is memory bound - the symptoms are odd and I don't really understand them - so maybe someone can first help me understand what I'm seeing..

I say that it appears memory bound because my dual-core CPU jumps from 20-70%, sometimes staying as low as 20% for extended periods during the calculation. It doesn't peg at 100% as I see with other functions I've written. I don't understand why.

The function I've written rotates vectors and propagates uncertainty through the calculation. It takes vector coordinates in the form of three matrices - one for x,y and z, matrices for roll, pitch and yaw angles, and then rotates each position vector through it's corresponding rotation angles. In addition the function takes uncertainty estimates (in the way of 3x3 covariance matrices embedded in a larger 3x3xMxN matrix) for each position and rotation and propagates these through the rotation producing a 3x3 covariance matrix for each xyz output triplet.

Because each rotation matrix and each Jacobian matrix (used to propagate the uncertainty) is unique, I have to manually loop through each combination of values, build the matrices, do the calculations, and assign them to the output.

The problem seems to be that I need to do this millions of times, and what I'm guessing is happening is that, to hold the input and output, so much memory is used that the resulting calculations are quite slow.

I have used the profiler and the lines that produce the most problem are very straight-foreward - matrix assignment or matrix multiplication or some combination - but things that I expect MATLAB to be quite fast at. In fact, I've thought to try to code the routine up in C, but I'm fearful that the result will be just as slow if I use MEX arrays and routines for multiplication.

I apologize this is a kind of fluffy request. I can show you code if that is more helpful.

Thanks in advance,

Val
From: vortse a on 21 Apr 2010 20:14
There is an undocumented feature in the matlab profiler which enables tracking of memory usage as well as JIT acceleration. This should help you find out if the slowdown is memory related.

http://undocumentedmatlab.com/blog/undocumented-profiler-options/
From: Val Schmidt on 26 Apr 2010 07:59
I have largely solved my processing bottleneck problem and I thought it worth posting a not about it.

My task was to apply a rotation matrix to about 8.5 million vectors in a "reasonable" amount of time, and at the same time estimate the uncertainty in the resulting vectors given uncertainty in the rotation angles and starting position. For each rotation I had to build a 3x3 rotation matrix and for each uncertainty calculation I had to build a 3x6 Jacobian matrix, plus hold the input and output covariance matrices (6x6).

To do this, I broke the problem down into parts, executing rotations on pieces of the input data at ago. But the real improvement in speed came in two parts. The first was to put the rotation and Jacobian matrices in large, 4D, 3x3xrowsxcols and 3x6xrowsxcols matrices rather than cell arrays each containing a single matrix. I of course could not do this for the full 8.5 million vectors at once, and had to break it down into smaller pieces. Then I used a MATLAB Central contribution called mtimesx to do the math.

(http://www.mathworks.com/matlabcentral/fileexchange/25977-mtimesx-fast-matrix-multiply-with-multi-dimensional-support).

This is a fast replacement for the normal MATLAB routine for matrix multiplication. With the code comes several scripts for testing the speed of mtimesx with the MATLAB native equivalent, and while mtimesx does not produce significantly faster results on my architecture and version (intel Mac, vR2008b) for a simple matrix multiplication, it contains the ability to, matrix by matrix, large 4D arrays of matrices like those I described above in one execution. To do this in native MATLAB Code requires a double loop over the outer rows and columns and many more function calls.

The combination of doing the math in chunks small enough to hold in memory but not too small, using 4D arrays to hold the arrays of rotation and Jacobian matrices and the use of mtimesx to do the math on them decreased my computation time more than an order of magnitude!!!
 | 
Pages: 1
Prev: Help with Matlab hw!
Next: invert a large number of matrices