I want to code a solver for nonsingular systems of $N$ linear equations in $N$ unknowns (say up to $N=100$) with an asymmetric Toeplitz matrix. I know that the Levinson algorithm can solve it in time $O(N^2)$ and I am looking for a solution with this complexity. I have seen mentions of alternative approaches such as Schur decomposition, LDU decomposition, Bareiss, Cholesky...

The equations are established in a Galois field, so that stability is not at all an issue here.

I am seeking advice for a good method to implement. My priorities are

  1. ease of implementation,

  2. low memory requirements.

I am not specially looking for superfast methods ($o(N^2)$), unless they are appropriate for moderate $N$, and simple.

What do you recommend?

  • $\begingroup$ Why don't you simply implement the Levinson algorithm? Do you think it's memory requirements are not low enough? Or do you just want somebody to confirm that the Levinson algorithm satisfies all your requirements? $\endgroup$ – Thomas Klimpel Mar 24 '14 at 0:20
  • $\begingroup$ I find it complicated and I am wondering if there could be better ones among alternative solutions. $\endgroup$ – Yves Daoust Mar 24 '14 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.