1

I have a calculation that requires the inverse of the weighted sum of two Toeplitz matrices aT1 + bT2 for many different weights a,b. Inverting T1, T2 or aT1+bT2 is an O(n^2) operation using Levinson/Trench. I have to repeat that for each a,b and that is the dominant effort in my problem. So I would like to find a way of inverting T1 and T2 separately once and for all and then somehow with less than O(n^2) effort get the first row of the inverse of aT1 +bT2 for each a,b

Paul
  • 11
  • Given the form of your data I suspect that you might be able to recast it as an FFT-type problem and at least get your time down to O(n log n) relatively straightforwardly. – Steven Stadnicki Apr 28 '20 at 17:38
  • I looked at the superfast algorithms but they're not all they're cracked up to be. O(n log n) turned out to be more like O(6n log 2n) – Paul Apr 29 '20 at 03:42
  • IFF the Toeplitz matrices T1 and T2 were cyclic shift matrices it would be easier because both would be diagonalized by the same DFT matrix i.e T1 = W(d2) W# and T2 = W(d2)W# so aT1+bT2 inverse is just – Paul Apr 29 '20 at 03:45

0 Answers0