CODEWITHSUNDEEP
algorithmmatrixlinear-algebra
eivour
eivour

Reputation: 1787

Algorithm to solve linear equation system without explicitly spelling out the matrix components

I have a linear function(n inputs -> n outputs), and using special structure of the function(some DP-like algorithm), I can evaluate the output in O(n) time, rather than O(n^2) time. Now, given some output values, I need to find the input that evaluates to the output.

I could spell out the matrix components(by evaluating the linear function with n basis inputs) and use some algorithms like LU decomposition, but that would take O(n^3) time to calculate. Is there a faster algorithm, exploiting the structure of the linear function?

(Since the linear function is not symmetric, Conjugate Gradient method could not be used.)

I need exact solutions, where n is small(n=10~20), but I need to do this kind of calculation hundreds of thousands of times in a second.

From code-design point of view, it would be better if the algorithm did not require transpose of the linear function. (Although at the cost of more code and more debugging, it is possible to provide transpose function with O(n) time complexity.)

Upvotes: 2

Views: 310

Answers (1)

kevmo314
kevmo314

Reputation: 4317

Have you considered GMRES? You mentioned that you're looking for exact solutions, however you can get within machine precision error reasonably quickly.

I can evaluate the output in O(n) time, rather than O(n^2) time.

You can use a linear operator to take advantage of this, for example with the GMRES in scipy implementation, A can be a LinearOperator. A linear operator is just a function that evaluates Ax, which is your "evaluate the output" step.

Otherwise, short of an ad hoc solution, I'm not familiar with any exact methods that can be accelerated with linear operators, so I'd need to know more about your problem, eg is your matrix banded?

Upvotes: 2

Related Questions