Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- AMD Community
- Communities
- Developers
- Devgurus Archives
- Archives Discussions
- Best GPU algorithm for solving 4x4 linear equation...

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

02-16-2012
01:20 PM

Best GPU algorithm for solving 4x4 linear equation system

Hi,

What is the best GPU algorithm for solving a linear equation system Ax = b, where A is a 4x4 or 3x3 matrix?

The equation is to be solved in one work item.

Thank you in advance!

Vis Cocoa

10 Replies

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

02-16-2012
04:04 PM

I'm not aware of a backslash operator available yet for OpenCL. Does anyone know of one? If so, we'd love to add it to Jacket and ArrayFire.

Also, I assume you're going to do many 4x4 or 3x3 matrices in a big batch. Doing just one of these is going to be slower on the GPU than it would be on the CPU (i.e. not enough data to get benefit from exploiting data-parallelism).

-John

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

02-16-2012
04:27 PM

I have just got an idea for 3x3

[a b c] x = d

det [a b c] = dot (a, cross (b, c));

det [d b c] = dot (d, cross (b, c));

det [a d c] = dot (a, cross (d, c));

det [a b d] = dot (a, cross (b, d));

x = (float3)(det[d b c], det [a d c], det [a b d]) / det [a b c];

Seems to be an efficient way? Any better ideas?

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

02-16-2012
05:13 PM

Your 3x3 method assumes the matrix is invertible. Is that guaranteed for your case?

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

02-16-2012
05:21 PM

Hi Jeff,

Nice to see your reply. No, the matrix is not guaranteed to be invertible. I wonder what if A is a singular matrix? I hope it results in an infinite float number

I have not make the kernel work yet. I am currently struggling with printf, which sometimes prints wrong characters, sometimes does not work at all. I appreciate if you give me some ideas on printing floats.

Thank you!

Vis Cocoa

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

02-16-2012
05:27 PM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

02-16-2012
11:53 PM

Thanks Jeff.

For Ax = b, if A is singular, the equation has either no solutions or infinitely many solutions.

I am working on a ray tracer. I can safely treat both cases as no solutions.

I have tested the triple product based method. It is more efficient than my previous method using scalar calculations

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

03-06-2012
01:24 PM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

02-16-2012
04:28 PM

thank you John!

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

02-16-2012
07:11 PM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

02-17-2012
12:00 AM

Hi AlexV,

Thank you very much for so many good ideas. I need to solve a small equation system in each work item, rather than solving a big equation for all work items. Therefore, it would be inefficient to move the work to CPU.

When working on CPUs, I like Singular-Value-Decomposition based method. A CPU core is much more powerful than a GPU core