Re: [eigen] Golub-Kahan bidiagonalization |

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]

*To*: eigen@xxxxxxxxxxxxxxxxxxx*Subject*: Re: [eigen] Golub-Kahan bidiagonalization*From*: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>*Date*: Thu, 30 Apr 2009 14:04:39 +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=ngerD3RxqBr9YWq//crzWrAjCNVpBDGEigbGBIGSY60=; b=pUQG/eV6/TnFEgVohOIR0IQioctVOVdiusSWWgZBCOoltRXUTxrIw0+8Ggagxa46ZK WArINOaGS187OVs4Isl6ir5yW5wA7Hpro7pzsw6vTNivYxY4gC3GVOPYC1jksh38qebg jWy2lwGFqeEfqDDacwWTAOSO0/QNBV9SoC/kU=*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=anO+jG9ehpY1OiA2+Xnv+Vq9gKkJlzV1YwiqeVtlUYxsaCfIhBYZm8RK7HG5521YhT QmRZGPm7pnEUfyeJPXAUU8lfoYFRC5qUUeAj7aP9vwQ/NJRK6D0hsW2bClDWOpOOoDJJ eF6pGJPlE2M1JTbvikf4V46stATZ0HEh35Cv8=

The additional cost of full pivoting, theoretically, is (2/3)n^3, while the cost without pivoting is already (8/3)n^3. So I don't expect it to be worth it, to first do a try without pivoting. Moreover, since we're a template library, this would mean twice the binary code size. Benoit 2009/4/29 Schleimer, Ben <bensch128@xxxxxxxxx>: > > Hi Benoit, > It might be useful for there to be a third bidiagonalization class which takes in an epsilon. It would run the partial pivoting version first and then check the error. If it's greater then epsilon, then it would run the full pivoting solution. I don't know how much overhead the error calculation would add but it might be worth it to make the api simpler.. > > just my two cents, > Ben > > > > --- On Tue, 4/28/09, Benoit Jacob <jacob.benoit.1@xxxxxxxxx> wrote: > >> From: Benoit Jacob <jacob.benoit.1@xxxxxxxxx> >> Subject: [eigen] Golub-Kahan bidiagonalization >> To: eigen@xxxxxxxxxxxxxxxxxxx >> Date: Tuesday, April 28, 2009, 6:28 AM >> Hi, >> >> this is mostly a followup to an old conversation with Keir >> as things >> are a little clearer in my mind now, but also to gather >> some feedback >> if there is an expert around. >> >> what i discuss here applies equally to tridiagonalization >> and >> Hessenberg reduction. >> >> 1) instability in the Golub-Kahan bidiagonalization >> algorithm. >> >> This is algorithm 5.4.2 in Golub&vanLoan, called >> "Householder >> bidiagonalization". >> >> It consists in left-multiplying by a Householder reflection >> to put the >> first column in the form (x,0,...,0), then >> right-multiplying by >> another Householder reflection to put the remainder of the >> first row >> (that is, without the 1st entry) in the form (y,0,....,0), >> and so on. >> >> The problem that I see is that if some column is close to >> zero, then a >> small perturbation of it results in a large perturbation of >> the >> corresponding Householder vector. This is because the >> Householder >> vector is normalized, and so this amounts to normalizing a >> near-zero >> vector. Additional instability comes from the fact that >> this involves >> taking the square root of a near-zero number (to compute >> the norm). >> >> 2) proposed solution: full pivoting >> >> Alongside plain bidiagonalization, we could offer a variant >> doing as >> follows. It would be slower but more reliable. >> >> At every step, before computing the Householder vector of a >> column, we >> could look up the (squared) norms of all remaining columns >> and permute >> columns to make the biggest remaining column the one that >> we are >> putting in form (x,0....,0). Same for rows. These >> permutation matrices >> being unitaries, fit perfectly in the decomposition which >> is already >> of the form UAV with U,V two independent unitaries. >> >> Since Golub-Kahan bidiagonalization already has (8/3)n^3 >> complexity, >> the overhead of full pivoting here would be a bit lower >> than it is for >> LU. >> >> 3) API for that. >> >> standard Bidiagonalization and pivoting Bidiagonalization >> would be 2 >> separate classes, but they could have a common base class >> abstracting >> that difference away from the SVD. The QR iteration to >> compute the SVD >> is the same in both cases. >> >> Cheers, >> Benoit >> >> >> > > >

**References**:**Re: [eigen] Golub-Kahan bidiagonalization***From:*Schleimer, Ben

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] operator= in SparseMatrixBase** - Next by Date:
**Re: [eigen] operator= in SparseMatrixBase** - Previous by thread:
**Re: [eigen] Golub-Kahan bidiagonalization** - Next by thread:
**[eigen] git**

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