Hi, I developed a vi that can be used to solve block tridiagonal systems of equations by Thomas Algorithm. Such systems are usually found in finite difference method used to solve partial differential equations. For 1,000 times iterations, its elapsed time is ~500ms. Now, I want to finish the job within 100ms. Is there any way to improve the performance? Thanks, Jong Hyun * For details of the Thomas algorithm, please refer to wikipedia webpage, http://en.wikipedia.org/wiki/Thomas_algorithm. Please note that it describes how to solve tridiagonal linear equations, but same logic can be applied to block tridiagonal equations. * If you use the Sparse SLE vi of Multicore Analysis and Sparse Matrix Toolkit, the elapsed time is ~450ms.

LabVIEW base/full/pro all use Intel's MKL library for linear algebra on MS Windows and Linux. Intel has designed MKL to be very fast for large matrices, and breaks a given problem apart to take advantage of the different levels of cache. The linear algebra calls go through several layers of functions, including size checks where appropriate, and may allocate workspace memory each call, before finally computing the result. This fixed overhead is readily apparent when the matrix is so small (3x3). I coded versions of the matrix-matrix multiply, matrix-vector multiply, and matrix inverse for the 3x3 case explicitly in G using the in-place element structure and full indexing (no loops, all scalar operations). This eliminates the overhead of checks, and allows better in-placeness. Doing this brings your benchmark down to ~70ms on my machine. Unfortunately this requires non-trivial code changes if you change the block size, but it does deliver good performance. "I think, if I can record the each inverse submatrix in the first iteration and use them repeatedly, then speed will be better." I agree. You should be able to pre-compute most of the forward sweep portion of the algorithm, and just replace the changed sub-matrices and continue the forward solve. This may mean re-arranging the variables to have the updated/changed sub-matrices at the lower right of the input matrix. -Jim

LabVIEW

Solve Linear Equations - Block Tridiagonal Matrix

Solved!

Author

Results are very interesting.

Thanks for another great update.

Message 11 of 11

(311 Views)

LabVIEW

Solve Linear Equations - Block Tridiagonal Matrix

Re: Solve Linear Equations - Block Tridiagonal Matrix