LAPACK 3.11.0
LAPACK: Linear Algebra PACKage
Loading...
Searching...
No Matches
cunhr_col.f
Go to the documentation of this file.
1*> \brief \b CUNHR_COL
2*
3* =========== DOCUMENTATION ===========
4*
5* Online html documentation available at
6* http://www.netlib.org/lapack/explore-html/
7*
8*> \htmlonly
9*> Download CUNHR_COL + dependencies
10*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.tgz?format=tgz&filename=/lapack/lapack_routine/cunhr_col.f">
11*> [TGZ]</a>
12*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.zip?format=zip&filename=/lapack/lapack_routine/cunhr_col.f">
13*> [ZIP]</a>
14*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.txt?format=txt&filename=/lapack/lapack_routine/cunhr_col.f">
15*> [TXT]</a>
16*> \endhtmlonly
17*>
18* Definition:
19* ===========
20*
21* SUBROUTINE CUNHR_COL( M, N, NB, A, LDA, T, LDT, D, INFO )
22*
23* .. Scalar Arguments ..
24* INTEGER INFO, LDA, LDT, M, N, NB
25* ..
26* .. Array Arguments ..
27* COMPLEX A( LDA, * ), D( * ), T( LDT, * )
28* ..
29*
30*> \par Purpose:
31* =============
32*>
33*> \verbatim
34*>
35*> CUNHR_COL takes an M-by-N complex matrix Q_in with orthonormal columns
36*> as input, stored in A, and performs Householder Reconstruction (HR),
37*> i.e. reconstructs Householder vectors V(i) implicitly representing
38*> another M-by-N matrix Q_out, with the property that Q_in = Q_out*S,
39*> where S is an N-by-N diagonal matrix with diagonal entries
40*> equal to +1 or -1. The Householder vectors (columns V(i) of V) are
41*> stored in A on output, and the diagonal entries of S are stored in D.
42*> Block reflectors are also returned in T
43*> (same output format as CGEQRT).
44*> \endverbatim
45*
46* Arguments:
47* ==========
48*
49*> \param[in] M
50*> \verbatim
51*> M is INTEGER
52*> The number of rows of the matrix A. M >= 0.
53*> \endverbatim
54*>
55*> \param[in] N
56*> \verbatim
57*> N is INTEGER
58*> The number of columns of the matrix A. M >= N >= 0.
59*> \endverbatim
60*>
61*> \param[in] NB
62*> \verbatim
63*> NB is INTEGER
64*> The column block size to be used in the reconstruction
65*> of Householder column vector blocks in the array A and
66*> corresponding block reflectors in the array T. NB >= 1.
67*> (Note that if NB > N, then N is used instead of NB
68*> as the column block size.)
69*> \endverbatim
70*>
71*> \param[in,out] A
72*> \verbatim
73*> A is COMPLEX array, dimension (LDA,N)
74*>
75*> On entry:
76*>
77*> The array A contains an M-by-N orthonormal matrix Q_in,
78*> i.e the columns of A are orthogonal unit vectors.
79*>
80*> On exit:
81*>
82*> The elements below the diagonal of A represent the unit
83*> lower-trapezoidal matrix V of Householder column vectors
84*> V(i). The unit diagonal entries of V are not stored
85*> (same format as the output below the diagonal in A from
86*> CGEQRT). The matrix T and the matrix V stored on output
87*> in A implicitly define Q_out.
88*>
89*> The elements above the diagonal contain the factor U
90*> of the "modified" LU-decomposition:
91*> Q_in - ( S ) = V * U
92*> ( 0 )
93*> where 0 is a (M-N)-by-(M-N) zero matrix.
94*> \endverbatim
95*>
96*> \param[in] LDA
97*> \verbatim
98*> LDA is INTEGER
99*> The leading dimension of the array A. LDA >= max(1,M).
100*> \endverbatim
101*>
102*> \param[out] T
103*> \verbatim
104*> T is COMPLEX array,
105*> dimension (LDT, N)
106*>
107*> Let NOCB = Number_of_output_col_blocks
108*> = CEIL(N/NB)
109*>
110*> On exit, T(1:NB, 1:N) contains NOCB upper-triangular
111*> block reflectors used to define Q_out stored in compact
112*> form as a sequence of upper-triangular NB-by-NB column
113*> blocks (same format as the output T in CGEQRT).
114*> The matrix T and the matrix V stored on output in A
115*> implicitly define Q_out. NOTE: The lower triangles
116*> below the upper-triangular blocks will be filled with
117*> zeros. See Further Details.
118*> \endverbatim
119*>
120*> \param[in] LDT
121*> \verbatim
122*> LDT is INTEGER
123*> The leading dimension of the array T.
124*> LDT >= max(1,min(NB,N)).
125*> \endverbatim
126*>
127*> \param[out] D
128*> \verbatim
129*> D is COMPLEX array, dimension min(M,N).
130*> The elements can be only plus or minus one.
131*>
132*> D(i) is constructed as D(i) = -SIGN(Q_in_i(i,i)), where
133*> 1 <= i <= min(M,N), and Q_in_i is Q_in after performing
134*> i-1 steps of “modified” Gaussian elimination.
135*> See Further Details.
136*> \endverbatim
137*>
138*> \param[out] INFO
139*> \verbatim
140*> INFO is INTEGER
141*> = 0: successful exit
142*> < 0: if INFO = -i, the i-th argument had an illegal value
143*> \endverbatim
144*>
145*> \par Further Details:
146* =====================
147*>
148*> \verbatim
149*>
150*> The computed M-by-M unitary factor Q_out is defined implicitly as
151*> a product of unitary matrices Q_out(i). Each Q_out(i) is stored in
152*> the compact WY-representation format in the corresponding blocks of
153*> matrices V (stored in A) and T.
154*>
155*> The M-by-N unit lower-trapezoidal matrix V stored in the M-by-N
156*> matrix A contains the column vectors V(i) in NB-size column
157*> blocks VB(j). For example, VB(1) contains the columns
158*> V(1), V(2), ... V(NB). NOTE: The unit entries on
159*> the diagonal of Y are not stored in A.
160*>
161*> The number of column blocks is
162*>
163*> NOCB = Number_of_output_col_blocks = CEIL(N/NB)
164*>
165*> where each block is of order NB except for the last block, which
166*> is of order LAST_NB = N - (NOCB-1)*NB.
167*>
168*> For example, if M=6, N=5 and NB=2, the matrix V is
169*>
170*>
171*> V = ( VB(1), VB(2), VB(3) ) =
172*>
173*> = ( 1 )
174*> ( v21 1 )
175*> ( v31 v32 1 )
176*> ( v41 v42 v43 1 )
177*> ( v51 v52 v53 v54 1 )
178*> ( v61 v62 v63 v54 v65 )
179*>
180*>
181*> For each of the column blocks VB(i), an upper-triangular block
182*> reflector TB(i) is computed. These blocks are stored as
183*> a sequence of upper-triangular column blocks in the NB-by-N
184*> matrix T. The size of each TB(i) block is NB-by-NB, except
185*> for the last block, whose size is LAST_NB-by-LAST_NB.
186*>
187*> For example, if M=6, N=5 and NB=2, the matrix T is
188*>
189*> T = ( TB(1), TB(2), TB(3) ) =
190*>
191*> = ( t11 t12 t13 t14 t15 )
192*> ( t22 t24 )
193*>
194*>
195*> The M-by-M factor Q_out is given as a product of NOCB
196*> unitary M-by-M matrices Q_out(i).
197*>
198*> Q_out = Q_out(1) * Q_out(2) * ... * Q_out(NOCB),
199*>
200*> where each matrix Q_out(i) is given by the WY-representation
201*> using corresponding blocks from the matrices V and T:
202*>
203*> Q_out(i) = I - VB(i) * TB(i) * (VB(i))**T,
204*>
205*> where I is the identity matrix. Here is the formula with matrix
206*> dimensions:
207*>
208*> Q(i){M-by-M} = I{M-by-M} -
209*> VB(i){M-by-INB} * TB(i){INB-by-INB} * (VB(i))**T {INB-by-M},
210*>
211*> where INB = NB, except for the last block NOCB
212*> for which INB=LAST_NB.
213*>
214*> =====
215*> NOTE:
216*> =====
217*>
218*> If Q_in is the result of doing a QR factorization
219*> B = Q_in * R_in, then:
220*>
221*> B = (Q_out*S) * R_in = Q_out * (S * R_in) = Q_out * R_out.
222*>
223*> So if one wants to interpret Q_out as the result
224*> of the QR factorization of B, then the corresponding R_out
225*> should be equal to R_out = S * R_in, i.e. some rows of R_in
226*> should be multiplied by -1.
227*>
228*> For the details of the algorithm, see [1].
229*>
230*> [1] "Reconstructing Householder vectors from tall-skinny QR",
231*> G. Ballard, J. Demmel, L. Grigori, M. Jacquelin, H.D. Nguyen,
232*> E. Solomonik, J. Parallel Distrib. Comput.,
233*> vol. 85, pp. 3-31, 2015.
234*> \endverbatim
235*>
236* Authors:
237* ========
238*
239*> \author Univ. of Tennessee
240*> \author Univ. of California Berkeley
241*> \author Univ. of Colorado Denver
242*> \author NAG Ltd.
243*
244*> \ingroup complexOTHERcomputational
245*
246*> \par Contributors:
247* ==================
248*>
249*> \verbatim
250*>
251*> November 2019, Igor Kozachenko,
252*> Computer Science Division,
253*> University of California, Berkeley
254*>
255*> \endverbatim
256*
257* =====================================================================
258 SUBROUTINE cunhr_col( M, N, NB, A, LDA, T, LDT, D, INFO )
259 IMPLICIT NONE
260*
261* -- LAPACK computational routine --
262* -- LAPACK is a software package provided by Univ. of Tennessee, --
263* -- Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..--
264*
265* .. Scalar Arguments ..
266 INTEGER INFO, LDA, LDT, M, N, NB
267* ..
268* .. Array Arguments ..
269 COMPLEX A( LDA, * ), D( * ), T( LDT, * )
270* ..
271*
272* =====================================================================
273*
274* .. Parameters ..
275 COMPLEX CONE, CZERO
276 parameter( cone = ( 1.0e+0, 0.0e+0 ),
277 $ czero = ( 0.0e+0, 0.0e+0 ) )
278* ..
279* .. Local Scalars ..
280 INTEGER I, IINFO, J, JB, JBTEMP1, JBTEMP2, JNB,
281 $ NPLUSONE
282* ..
283* .. External Subroutines ..
285 $ xerbla
286* ..
287* .. Intrinsic Functions ..
288 INTRINSIC max, min
289* ..
290* .. Executable Statements ..
291*
292* Test the input parameters
293*
294 info = 0
295 IF( m.LT.0 ) THEN
296 info = -1
297 ELSE IF( n.LT.0 .OR. n.GT.m ) THEN
298 info = -2
299 ELSE IF( nb.LT.1 ) THEN
300 info = -3
301 ELSE IF( lda.LT.max( 1, m ) ) THEN
302 info = -5
303 ELSE IF( ldt.LT.max( 1, min( nb, n ) ) ) THEN
304 info = -7
305 END IF
306*
307* Handle error in the input parameters.
308*
309 IF( info.NE.0 ) THEN
310 CALL xerbla( 'CUNHR_COL', -info )
311 RETURN
312 END IF
313*
314* Quick return if possible
315*
316 IF( min( m, n ).EQ.0 ) THEN
317 RETURN
318 END IF
319*
320* On input, the M-by-N matrix A contains the unitary
321* M-by-N matrix Q_in.
322*
323* (1) Compute the unit lower-trapezoidal V (ones on the diagonal
324* are not stored) by performing the "modified" LU-decomposition.
325*
326* Q_in - ( S ) = V * U = ( V1 ) * U,
327* ( 0 ) ( V2 )
328*
329* where 0 is an (M-N)-by-N zero matrix.
330*
331* (1-1) Factor V1 and U.
332
333 CALL claunhr_col_getrfnp( n, n, a, lda, d, iinfo )
334*
335* (1-2) Solve for V2.
336*
337 IF( m.GT.n ) THEN
338 CALL ctrsm( 'R', 'U', 'N', 'N', m-n, n, cone, a, lda,
339 $ a( n+1, 1 ), lda )
340 END IF
341*
342* (2) Reconstruct the block reflector T stored in T(1:NB, 1:N)
343* as a sequence of upper-triangular blocks with NB-size column
344* blocking.
345*
346* Loop over the column blocks of size NB of the array A(1:M,1:N)
347* and the array T(1:NB,1:N), JB is the column index of a column
348* block, JNB is the column block size at each step JB.
349*
350 nplusone = n + 1
351 DO jb = 1, n, nb
352*
353* (2-0) Determine the column block size JNB.
354*
355 jnb = min( nplusone-jb, nb )
356*
357* (2-1) Copy the upper-triangular part of the current JNB-by-JNB
358* diagonal block U(JB) (of the N-by-N matrix U) stored
359* in A(JB:JB+JNB-1,JB:JB+JNB-1) into the upper-triangular part
360* of the current JNB-by-JNB block T(1:JNB,JB:JB+JNB-1)
361* column-by-column, total JNB*(JNB+1)/2 elements.
362*
363 jbtemp1 = jb - 1
364 DO j = jb, jb+jnb-1
365 CALL ccopy( j-jbtemp1, a( jb, j ), 1, t( 1, j ), 1 )
366 END DO
367*
368* (2-2) Perform on the upper-triangular part of the current
369* JNB-by-JNB diagonal block U(JB) (of the N-by-N matrix U) stored
370* in T(1:JNB,JB:JB+JNB-1) the following operation in place:
371* (-1)*U(JB)*S(JB), i.e the result will be stored in the upper-
372* triangular part of T(1:JNB,JB:JB+JNB-1). This multiplication
373* of the JNB-by-JNB diagonal block U(JB) by the JNB-by-JNB
374* diagonal block S(JB) of the N-by-N sign matrix S from the
375* right means changing the sign of each J-th column of the block
376* U(JB) according to the sign of the diagonal element of the block
377* S(JB), i.e. S(J,J) that is stored in the array element D(J).
378*
379 DO j = jb, jb+jnb-1
380 IF( d( j ).EQ.cone ) THEN
381 CALL cscal( j-jbtemp1, -cone, t( 1, j ), 1 )
382 END IF
383 END DO
384*
385* (2-3) Perform the triangular solve for the current block
386* matrix X(JB):
387*
388* X(JB) * (A(JB)**T) = B(JB), where:
389*
390* A(JB)**T is a JNB-by-JNB unit upper-triangular
391* coefficient block, and A(JB)=V1(JB), which
392* is a JNB-by-JNB unit lower-triangular block
393* stored in A(JB:JB+JNB-1,JB:JB+JNB-1).
394* The N-by-N matrix V1 is the upper part
395* of the M-by-N lower-trapezoidal matrix V
396* stored in A(1:M,1:N);
397*
398* B(JB) is a JNB-by-JNB upper-triangular right-hand
399* side block, B(JB) = (-1)*U(JB)*S(JB), and
400* B(JB) is stored in T(1:JNB,JB:JB+JNB-1);
401*
402* X(JB) is a JNB-by-JNB upper-triangular solution
403* block, X(JB) is the upper-triangular block
404* reflector T(JB), and X(JB) is stored
405* in T(1:JNB,JB:JB+JNB-1).
406*
407* In other words, we perform the triangular solve for the
408* upper-triangular block T(JB):
409*
410* T(JB) * (V1(JB)**T) = (-1)*U(JB)*S(JB).
411*
412* Even though the blocks X(JB) and B(JB) are upper-
413* triangular, the routine CTRSM will access all JNB**2
414* elements of the square T(1:JNB,JB:JB+JNB-1). Therefore,
415* we need to set to zero the elements of the block
416* T(1:JNB,JB:JB+JNB-1) below the diagonal before the call
417* to CTRSM.
418*
419* (2-3a) Set the elements to zero.
420*
421 jbtemp2 = jb - 2
422 DO j = jb, jb+jnb-2
423 DO i = j-jbtemp2, nb
424 t( i, j ) = czero
425 END DO
426 END DO
427*
428* (2-3b) Perform the triangular solve.
429*
430 CALL ctrsm( 'R', 'L', 'C', 'U', jnb, jnb, cone,
431 $ a( jb, jb ), lda, t( 1, jb ), ldt )
432*
433 END DO
434*
435 RETURN
436*
437* End of CUNHR_COL
438*
439 END
subroutine xerbla(SRNAME, INFO)
XERBLA
Definition: xerbla.f:60
subroutine ccopy(N, CX, INCX, CY, INCY)
CCOPY
Definition: ccopy.f:81
subroutine cscal(N, CA, CX, INCX)
CSCAL
Definition: cscal.f:78
subroutine ctrsm(SIDE, UPLO, TRANSA, DIAG, M, N, ALPHA, A, LDA, B, LDB)
CTRSM
Definition: ctrsm.f:180
subroutine claunhr_col_getrfnp(M, N, A, LDA, D, INFO)
CLAUNHR_COL_GETRFNP
subroutine cunhr_col(M, N, NB, A, LDA, T, LDT, D, INFO)
CUNHR_COL
Definition: cunhr_col.f:259