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

**References**:**[eigen] cache-friendly matrix inverse***From:*Benoit Jacob

**Re: [eigen] cache-friendly matrix inverse***From:*Christian Mayer

**Re: [eigen] cache-friendly matrix inverse***From:*Robert Lupton the Good

**Re: [eigen] cache-friendly matrix inverse***From:*Christian Mayer

**Re: [eigen] cache-friendly matrix inverse***From:*Robert Lupton the Good

**Re: [eigen] cache-friendly matrix inverse***From:*Christian Mayer

**Re: [eigen] cache-friendly matrix inverse***From:*Benoit Jacob

**Re: [eigen] cache-friendly matrix inverse***From:*Christian Mayer

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] cache-friendly matrix inverse** - Next by Date:
**Re: [eigen] cache-friendly matrix inverse** - Previous by thread:
**Re: [eigen] cache-friendly matrix inverse** - Next by thread:
**Re: [eigen] cache-friendly matrix inverse**

Mail converted by MHonArc 2.6.19+ | http://listengine.tuxfamily.org/ |