5 ms·

I haven't looked into it in years, but would the inverse of a block bi-diagonal matrix have some semiseperable structure? Maybe that would be good to look into

• rahimiali 8mo ago
  just to be clear, semiseparate in this context means H = D + CC', where D is block diagonal and C is tall & skinny? If so, it would be nice if this were the case, because you could then just use the Woodbury formula to invert H. But I don't think such a decomposition exists. I tried to exhaustively search through all the decompositions of H that involved one dummy variable (of which the above is a special case) and I couldn't find one. I ended up having to introduce two dummy variables instead.
  • jeffjeffbear 8mo ago
    > just to be clear, semiseparate in this context means H = D + CC', where D is block diagonal and C is tall & skinny? Not quite, it means any submatrix taken from the upper(lower) part of the matrix has some low rank. Like a matrix is {3,4}-semiseperable if any sub matrix taken from the lower triangular part has at most rank 3 and any submatrix taken from the upper triangular part has at most rank 4. The inverse of an upper bidiagonal matrix is {0,1}-semiseperable. There are a lot of fast algorithms if you know a matrix is semiseperable. edit: link https://people.cs.kuleuven.be/~raf.vandebril/homepage/publications/papers_html/qrq_07/node16.html https://people.cs.kuleuven.be/~raf.vandebril/homepage/public...
    • rahimiali 8mo ago
      thanks for the explanation! sorry i had misread the AI summary on "semiseparable". i need to firm my intuition on this first before i can say anything clever, but i agree it's worth thinking about!