Re: [eigen] [PATCH] Toeplitz matrix specialization

[Keir Mierle <mierle@xxxxxxxxx>]

On Thu, Jan 29, 2009 at 11:36 AM, Gael Guennebaud
<gael.guennebaud@xxxxxxxxx> wrote:
> On Thu, Jan 29, 2009 at 7:55 PM, Keir Mierle <mierle@xxxxxxxxx> wrote:
>> On Thu, Jan 29, 2009 at 6:40 AM, Gael Guennebaud
>> <gael.guennebaud@xxxxxxxxx> wrote:
>>> Hi,
>>>
>>> to start the debate I put some thougths on the wiki:
>>> http://eigen.tuxfamily.org/index.php?title=SpecialMatrix
>>
>> The idea of making solveTriangular into Part::solve() sounds good to
>> me. Right now the hetergeneous API for solving triangular systems is
>> unfortunate. I vote to have solve() work as expected for triangular
>> matrices with the same API as LU::solve, SVD::solve, QR::solve, etc
>> (i.e. MyVec x; bool succeeded = my_triangular_mat.solve(b, &x);).
>> Perhaps mymat.upperTriangular().solve(...)?
>
> yes, exactly.
>
>> Is there an excessive runtime cost to detecting a singular matrix in
>> the triangular solver?
>
> N comparisons, just like for Cholesky.

Is it possible to have a bit to mark the martix as invertible by the
user, to avoid the runtime cost? I.e. so that the check is optimized
away when the bit is set. However, we should benchmark the cost of
having the check to make sure it's high enough to want to remove.

Keir

>
> Gael.
>
>
>> Keir
>>
>>>
>>> Gael.
>>>
>>> On Thu, Jan 29, 2009 at 2:08 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx> wrote:
>>>> 2009/1/29 Mauro Iazzi <mauro.iazzi@xxxxxxxxx>:
>>>>> Hi, I'm still thinking about that...
>>>>> Is there any new idea on how to handle this problem?
>>>>>
>>>>> On a side note, wouldn't it be nice if sparse matrices were in the same class?
>>>>
>>>> Yes we had a quick discussion over IRC yesterday, and yes we evocated
>>>> the idea that these special matrices were often sparse and then they
>>>> should be designed with interaction also with Sparse in mind.
>>>>
>>>> Here's the log:
>>>>
>>>> [mer. janv. 28 2009] [18:23:03] <ggael> I'm thinking about the
>>>> SpecialMatrix mess with Special in {Diagonal, Tridigonal, Toeplitz,
>>>> Band}x{Normal,SelfAdjoint}.....
>>>> [mer. janv. 28 2009] [18:23:32] <bjacob> good that you're thinking
>>>> about that in such generality
>>>> [mer. janv. 28 2009] [18:23:35] <ggael> and I don't have an elegent
>>>> solution yet :(
>>>> [mer. janv. 28 2009] [18:24:24] <bjacob> i still am tempted by the
>>>> brutal solution of giving up having these as MatrixBase expressions...
>>>> [mer. janv. 28 2009] [18:25:14] <bjacob> they are as special as
>>>> SparseMatrix (many of them are actually sparse matrices)
>>>> [mer. janv. 28 2009] [18:25:28] <ggael> the main problem is the
>>>> explosion of combination.... (unless we give up about perf and keep
>>>> branching inside coeff())
>>>> [mer. janv. 28 2009] [18:26:04] <bjacob> that only is a problem if you
>>>> want to allow all sorts of operations seamlessly on these matrices
>>>> [mer. janv. 28 2009] [18:27:12] <bjacob> the problem goes away if we
>>>> only support these matrices as stupid containers for communicating
>>>> with algorithms (we'd still allow operator= on them to copy into a
>>>> MatrixBase, but that's all)
>>>> [mer. janv. 28 2009] [18:27:37] <bjacob> e.g. tridiagonalization would
>>>> return a TridiagonalMatrix that's just a struct with a few vectors
>>>> [mer. janv. 28 2009] [18:27:47] <bjacob> then you could do MatrixXd m = tridiag;
>>>> [mer. janv. 28 2009] [18:27:49] <ggael> yes, for Toeplitz this would make sense
>>>> [mer. janv. 28 2009] [18:28:49] <bjacob> i don't think there's much of
>>>> a use case for e.g. multiplying a tridiagonal matrix by a diagonal
>>>> matrix
>>>> [mer. janv. 28 2009] [18:29:05] <bjacob> so we only need to let each
>>>> special mat type interoperate with MatrixBase
>>>> [mer. janv. 28 2009] [18:29:16] <bjacob> but we don't need to let them
>>>> interoperate with each other
>>>> [mer. janv. 28 2009] [18:29:28] <bjacob> so O(n) stuff not O(n^2)
>>>> [mer. janv. 28 2009] [18:30:51] <ggael> ok, then that would be doable
>>>> without too much work
>>>> [mer. janv. 28 2009] [18:31:13] <bjacob> yep
>>>> [mer. janv. 28 2009] [18:31:50] <bjacob> something just occured to me
>>>> [mer. janv. 28 2009] [18:31:51] <ggael> also Toeplitz => special
>>>> module, too specific !
>>>> [mer. janv. 28 2009] [18:32:18] <bjacob> these special matrices would
>>>> be actually not closer to MatrixBase than SparseMatrixBase
>>>> [mer. janv. 28 2009] [18:32:43] <bjacob> we should probably right away
>>>> think of letting them be useful also for Sparse
>>>> [mer. janv. 28 2009] [18:33:58] <ggael> yes of course
>>>> [mer. janv. 28 2009] [18:34:31] <bjacob> i hope that what i just said
>>>> doesn't contradict your latest big commit (haven't looked yet)
>>>> [mer. janv. 28 2009] [18:36:27] <ggael> no, what my commit mainly did
>>>> is to add: DiagonalMatrix<Scalar,Size>, it currently inherits
>>>> MatrixBase but that can be changed later
>>>> [mer. janv. 28 2009] [18:37:14] <bjacob> ok
>>>>
>>>>
>>>>
>>>
>>>
>>>
>>
>>
>>
>
>
>