matrix inversion

[m_labbaf]

Hi everyone,

I want to create a simulator using Epiphany processor. During my simulator algorithm stages, I have Ax = b equation which x is unknown. A is 8x8 matrix and b is 8x1 vector.
The problem that I faced is limited time-step to solve this equations, so I should use parallel processing capability to reduce processing time.
I want to know which algorithm has better performance and is there anyone who implemented matrix inversion on epiphany?

thanks in advance

[piotr5]

you still didn't tell us how the value of x will be used in the next step of your algorithm! there might be possibilities to gain speed by preparing the output of x in a way that next step is done more quickly, maybe even the next matrix-inversion wouldn't be needed anymore and you could do 2 steps at once...

the simplest way to invert your matrix is by writing a generic set of equations (8x8=64 variables plus the 8 values of b and 8 entries for the unknown x, about 52 variables total if you're symmetric), doing a generic run of equation-solving, and then letting computer plug in values in the resulting formulas. also an interesting approach is to represent your matrix by a matrix of quaternions. or maybe use projective space with 9D vectors, and avoid rational numbers completely. it really depends on what you'll be doing with the result...

[m_labbaf]

Thanks for your advice,

I want to create a real-time circuit simulator using Epiphany, so I have a linear circuit that should solved in many steps and find the output.
for each circuit I write nodal equation (the size of nodal matrix is dependent to circuit topology) and solve it in every time-step. It's important to has low time-step(below 1us).
So in every time-step nodal matrix and input vector are updated and based on their values output (x vector) calculated.

A matrix and b vector is completely related to x result from previous step, so each step should solve independently.

I was thought about writing 8 equation with 52 variable that variables updated in each step, but it seems has some problem. First, it doesn't seems that equation has good forms for implementation. Second, it is limited to 8x8 matrix that could change for other application(changing circuit topology).

In this matrix all element are real number and I don't has any complex number. I don't know if projective space can help or not.

[piotr5]

you say each step should solve independently. does that mean there is an if-statement at each step to determine how it depends? if that's the case you could do something similar to branch-prediction, and calculate 2 steps in <2µs that way. i.e. use 2 processes in parallell, one starting at odd the other at even steps, and they communicate about the correct branch to take. alternatively, there is for sure a possibility to express if-statements in linear algebra, and you could just calculate multiple steps at once till you reach the speed you desire. if it's all just linear equations, your calculations will never become more complicated.

[m_labbaf]

The overall procedure is as below Pseudo code
for i: 1 - n (e.g. n= 16000000)
update A matrix and b vector based on previous step values
find x (output) based on A and b
some little calculation
end

So, There isn't any if statement to pipeline. I think the better solution related to better calculating algorithm for finding x vector(output).
Also, data forwarding between different step can be a good idea that may speedup implementation that I will think about it more in future.

[isee]

Depending on the nature of the update to the A matrix, after the inverse matrix has been computed for the first time
the inverse matrix could be updated using the Sherman–Morrison–Woodbury formula:

[url]https://en.wikipedia.org/wiki/Sherman–Morrison–Woodbury_formula[/url]

One method of computing the inverse matrix is an iterative solver called the "hyper-power"
method, which converges to the solution quadratically if the starting estimate of the inverse
is close to the correct solution. There is a reference to the method
on Wikipedia: