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?
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.
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.
Comments
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?
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.
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/public...
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!