| Re: [eigen] [RFC] Full pivoting LDLT |
[ Thread Index |
Date Index
| More lists.tuxfamily.org/eigen Archives
]
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] [RFC] Full pivoting LDLT
- From: Gael Guennebaud <gael.guennebaud@xxxxxxxxx>
- Date: Tue, 3 Feb 2009 11:05:37 +0100
- 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=lujofPQxyQP1um1dFdqsLtKt8sJSUxP2fcHVATu4MEo=; b=yEHUrvL2pbQirHonJetbe83BIpBtqsPgm1z5aZUaTDM39ltksJHWS1lXeh/ENG1TgY ++1X9TvA0lEj9iuzr9hP6vPzlBfjm38wIFI2thHbEZ4o4uy3m26SZ9MRHJsw1EI3sIxW Sec3+7Ph5GgBOo/RKVZMShWL6HVv6S39N6/tU=
- 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=WwXb0mtQ7NdODfrnD4h/jQM35c6oLA8B7aqN46euWqtr16Bf6L6qjRpAfpP50YhXpk gv10cAUk4v5EkTm1NaTmjxDUPOJpwd4hY/0TQSimNayWY94S4XtoV0WT1bidpVTVT2Wc 4IYkufdMBLmpDOLDweHNCPbH5ItrnNoLIBapA=
hi,
my initial concern about removing the current LDLT behavior was about
performance (LDLt avoid the need of sqrt). Here are some benchmark for
small fixed size between the current LDLt and LLt:
size no sqrt standard
fixed 2 0.00102645s (389.692 MFLOPS) 0.00183895s (217.515 MFLOPS)
fixed 3 0.00365066s (383.492 MFLOPS) 0.00431897s (324.152 MFLOPS)
fixed 4 0.00674173s (474.656 MFLOPS) 0.00709854s (450.797 MFLOPS)
fixed 5 0.015228s (394.01 MFLOPS) 0.0107528s (557.994 MFLOPS)
fixed 6 0.0210597s (474.84 MFLOPS) 0.0203626s (491.097 MFLOPS)
fixed 7 0.0291546s (528.218 MFLOPS) 0.0314288s (489.996 MFLOPS)
fixed 8 0.0511112s (438.26 MFLOPS) 0.0421623s (531.28 MFLOPS)
fixed 12 0.139711s (503.898 MFLOPS) 0.104209s (675.567 MFLOPS)
fixed 16 0.369657s (432.834 MFLOPS) 0.197822s (808.808 MFLOPS)
- for large size LLt is much faster than LDLt because the algorithm is
simpler (better cache friendliness, we can use fast matrix-vector
products, etc.)
- for very small sizes LDLt is not clearly better
- the solve operation for LDLt is more expensive than LLt because of
the product by D-1 (these bench does not include the solve step)
So all in all this is not going to be a big lost ! So go ahead !
gael.
On Tue, Feb 3, 2009 at 9:15 AM, Keir Mierle <mierle@xxxxxxxxx> wrote:
> http://codereview.appspot.com/14042/diff/1/4
>
> There are a couple of issues.
>
> 1. Pivoting is not optional. Any objections?
> 2. If the matrix is only semidefinite, then matrixL() gives wrong results
> (1's in diagonal where they shouldn't be).
>
> Minus objections, I'll commit this.
>
> Keir
>