| Re: [eigen] cache-friendly matrix inverse |
[ Thread Index |
Date Index
| More lists.tuxfamily.org/eigen Archives
]
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] cache-friendly matrix inverse
- From: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
- Date: Thu, 14 May 2009 00:20:32 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=+w7RFjI5zonDpkRj5TJP+J3szOo+cT/OD/+jcpmHvec=; b=gQGGtRe6gDaEAYaqZku27u4kgVORcLjbZDhUbJsXLtDazl7FKwYb0p7Ys/uxSK++41 voUNG9MW0vpSpMZovLOP1rHyucYVCvmUk6BT5DBVJbJ/ajMnKqmZdko3TV00O83z1RZl Xf0iWkt1yPceP4utSgjbD3IOradq5MNnQDFzY=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; b=QgLClIpmJdbwUDWywT36X+2ppKLKpBddxzjTzYiY0Yxb1LEkRiGvO047K0axUxo+e9 21GI2NudJ3LuCAkDAwCRcblXbJ2vCjN1HShdnQBaKm1lIvNPNvavUBHXjnuJIkrpNFPD ge0s4Pa2LKb3Rc4sTzj8atdlJnhPKXm+vsHXU=
2009/5/13, Christian Mayer <mail@xxxxxxxxxxxxxxxxx>:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> Benoit Jacob schrieb:
>> whenever they show up; then the best thing you can do is to precompute
>> A^-1 so you only have a matrix-vector product to compute whenever a
>> "b" vector shows up.
>
> That's *exacly* what LU decomposition is for. Compute it once and use it
> to solve the equation many times.
> Note: the amount of operations to calculate A^-1 and an LU decomposition
> is the same. *AND* using a LU to solve the equation (foreward and
> backward substitution) takes also as many operations as a matrix
> multiplication (i.e. exactly the same as a multiplication with the inverse)
Good point. I think you're right for very large sizes, asymptotically
they're the same.
But matrix-vector product is far easier to optimize than triangular
solver, and incurs less "startup" overhead, i'm thinking e.g. about
the pivoting permutation that you have to apply when using the LU with
partial pivoting to solve the equation, and also regarding
vectorization the triangular solver has more "unaligned boundaries" to
deal with. For large enough sizes that should be negligible.
But for a size like 10x10, the matrix-vector product will be much faster.
Cheers,
Benoit