LAPACK  3.10.0
LAPACK: Linear Algebra PACKage

◆ sorhr_col()

subroutine sorhr_col ( integer  M,
integer  N,
integer  NB,
real, dimension( lda, * )  A,
integer  LDA,
real, dimension( ldt, * )  T,
integer  LDT,
real, dimension( * )  D,
integer  INFO 
)

SORHR_COL

Download SORHR_COL + dependencies [TGZ] [ZIP] [TXT]

Purpose:
  SORHR_COL takes an M-by-N real matrix Q_in with orthonormal columns
  as input, stored in A, and performs Householder Reconstruction (HR),
  i.e. reconstructs Householder vectors V(i) implicitly representing
  another M-by-N matrix Q_out, with the property that Q_in = Q_out*S,
  where S is an N-by-N diagonal matrix with diagonal entries
  equal to +1 or -1. The Householder vectors (columns V(i) of V) are
  stored in A on output, and the diagonal entries of S are stored in D.
  Block reflectors are also returned in T
  (same output format as SGEQRT).
Parameters
[in]M
          M is INTEGER
          The number of rows of the matrix A. M >= 0.
[in]N
          N is INTEGER
          The number of columns of the matrix A. M >= N >= 0.
[in]NB
          NB is INTEGER
          The column block size to be used in the reconstruction
          of Householder column vector blocks in the array A and
          corresponding block reflectors in the array T. NB >= 1.
          (Note that if NB > N, then N is used instead of NB
          as the column block size.)
[in,out]A
          A is REAL array, dimension (LDA,N)

          On entry:

             The array A contains an M-by-N orthonormal matrix Q_in,
             i.e the columns of A are orthogonal unit vectors.

          On exit:

             The elements below the diagonal of A represent the unit
             lower-trapezoidal matrix V of Householder column vectors
             V(i). The unit diagonal entries of V are not stored
             (same format as the output below the diagonal in A from
             SGEQRT). The matrix T and the matrix V stored on output
             in A implicitly define Q_out.

             The elements above the diagonal contain the factor U
             of the "modified" LU-decomposition:
                Q_in - ( S ) = V * U
                       ( 0 )
             where 0 is a (M-N)-by-(M-N) zero matrix.
[in]LDA
          LDA is INTEGER
          The leading dimension of the array A.  LDA >= max(1,M).
[out]T
          T is REAL array,
          dimension (LDT, N)

          Let NOCB = Number_of_output_col_blocks
                   = CEIL(N/NB)

          On exit, T(1:NB, 1:N) contains NOCB upper-triangular
          block reflectors used to define Q_out stored in compact
          form as a sequence of upper-triangular NB-by-NB column
          blocks (same format as the output T in SGEQRT).
          The matrix T and the matrix V stored on output in A
          implicitly define Q_out. NOTE: The lower triangles
          below the upper-triangular blocks will be filled with
          zeros. See Further Details.
[in]LDT
          LDT is INTEGER
          The leading dimension of the array T.
          LDT >= max(1,min(NB,N)).
[out]D
          D is REAL array, dimension min(M,N).
          The elements can be only plus or minus one.

          D(i) is constructed as D(i) = -SIGN(Q_in_i(i,i)), where
          1 <= i <= min(M,N), and Q_in_i is Q_in after performing
          i-1 steps of “modified” Gaussian elimination.
          See Further Details.
[out]INFO
          INFO is INTEGER
          = 0:  successful exit
          < 0:  if INFO = -i, the i-th argument had an illegal value
Further Details:
 The computed M-by-M orthogonal factor Q_out is defined implicitly as
 a product of orthogonal matrices Q_out(i). Each Q_out(i) is stored in
 the compact WY-representation format in the corresponding blocks of
 matrices V (stored in A) and T.

 The M-by-N unit lower-trapezoidal matrix V stored in the M-by-N
 matrix A contains the column vectors V(i) in NB-size column
 blocks VB(j). For example, VB(1) contains the columns
 V(1), V(2), ... V(NB). NOTE: The unit entries on
 the diagonal of Y are not stored in A.

 The number of column blocks is

     NOCB = Number_of_output_col_blocks = CEIL(N/NB)

 where each block is of order NB except for the last block, which
 is of order LAST_NB = N - (NOCB-1)*NB.

 For example, if M=6,  N=5 and NB=2, the matrix V is


     V = (    VB(1),   VB(2), VB(3) ) =

       = (   1                      )
         ( v21    1                 )
         ( v31  v32    1            )
         ( v41  v42  v43   1        )
         ( v51  v52  v53  v54    1  )
         ( v61  v62  v63  v54   v65 )


 For each of the column blocks VB(i), an upper-triangular block
 reflector TB(i) is computed. These blocks are stored as
 a sequence of upper-triangular column blocks in the NB-by-N
 matrix T. The size of each TB(i) block is NB-by-NB, except
 for the last block, whose size is LAST_NB-by-LAST_NB.

 For example, if M=6,  N=5 and NB=2, the matrix T is

     T  = (    TB(1),    TB(2), TB(3) ) =

        = ( t11  t12  t13  t14   t15  )
          (      t22       t24        )


 The M-by-M factor Q_out is given as a product of NOCB
 orthogonal M-by-M matrices Q_out(i).

     Q_out = Q_out(1) * Q_out(2) * ... * Q_out(NOCB),

 where each matrix Q_out(i) is given by the WY-representation
 using corresponding blocks from the matrices V and T:

     Q_out(i) = I - VB(i) * TB(i) * (VB(i))**T,

 where I is the identity matrix. Here is the formula with matrix
 dimensions:

  Q(i){M-by-M} = I{M-by-M} -
    VB(i){M-by-INB} * TB(i){INB-by-INB} * (VB(i))**T {INB-by-M},

 where INB = NB, except for the last block NOCB
 for which INB=LAST_NB.

 =====
 NOTE:
 =====

 If Q_in is the result of doing a QR factorization
 B = Q_in * R_in, then:

 B = (Q_out*S) * R_in = Q_out * (S * R_in) = Q_out * R_out.

 So if one wants to interpret Q_out as the result
 of the QR factorization of B, then the corresponding R_out
 should be equal to R_out = S * R_in, i.e. some rows of R_in
 should be multiplied by -1.

 For the details of the algorithm, see [1].

 [1] "Reconstructing Householder vectors from tall-skinny QR",
     G. Ballard, J. Demmel, L. Grigori, M. Jacquelin, H.D. Nguyen,
     E. Solomonik, J. Parallel Distrib. Comput.,
     vol. 85, pp. 3-31, 2015.
Author
Univ. of Tennessee
Univ. of California Berkeley
Univ. of Colorado Denver
NAG Ltd.
Contributors:
 November   2019, Igor Kozachenko,
            Computer Science Division,
            University of California, Berkeley

Definition at line 258 of file sorhr_col.f.

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  REAL A( LDA, * ), D( * ), T( LDT, * )
270 * ..
271 *
272 * =====================================================================
273 *
274 * .. Parameters ..
275  REAL ONE, ZERO
276  parameter( one = 1.0e+0, zero = 0.0e+0 )
277 * ..
278 * .. Local Scalars ..
279  INTEGER I, IINFO, J, JB, JBTEMP1, JBTEMP2, JNB,
280  $ NPLUSONE
281 * ..
282 * .. External Subroutines ..
283  EXTERNAL scopy, slaorhr_col_getrfnp, sscal, strsm,
284  $ xerbla
285 * ..
286 * .. Intrinsic Functions ..
287  INTRINSIC max, min
288 * ..
289 * .. Executable Statements ..
290 *
291 * Test the input parameters
292 *
293  info = 0
294  IF( m.LT.0 ) THEN
295  info = -1
296  ELSE IF( n.LT.0 .OR. n.GT.m ) THEN
297  info = -2
298  ELSE IF( nb.LT.1 ) THEN
299  info = -3
300  ELSE IF( lda.LT.max( 1, m ) ) THEN
301  info = -5
302  ELSE IF( ldt.LT.max( 1, min( nb, n ) ) ) THEN
303  info = -7
304  END IF
305 *
306 * Handle error in the input parameters.
307 *
308  IF( info.NE.0 ) THEN
309  CALL xerbla( 'SORHR_COL', -info )
310  RETURN
311  END IF
312 *
313 * Quick return if possible
314 *
315  IF( min( m, n ).EQ.0 ) THEN
316  RETURN
317  END IF
318 *
319 * On input, the M-by-N matrix A contains the orthogonal
320 * M-by-N matrix Q_in.
321 *
322 * (1) Compute the unit lower-trapezoidal V (ones on the diagonal
323 * are not stored) by performing the "modified" LU-decomposition.
324 *
325 * Q_in - ( S ) = V * U = ( V1 ) * U,
326 * ( 0 ) ( V2 )
327 *
328 * where 0 is an (M-N)-by-N zero matrix.
329 *
330 * (1-1) Factor V1 and U.
331 
332  CALL slaorhr_col_getrfnp( n, n, a, lda, d, iinfo )
333 *
334 * (1-2) Solve for V2.
335 *
336  IF( m.GT.n ) THEN
337  CALL strsm( 'R', 'U', 'N', 'N', m-n, n, one, a, lda,
338  $ a( n+1, 1 ), lda )
339  END IF
340 *
341 * (2) Reconstruct the block reflector T stored in T(1:NB, 1:N)
342 * as a sequence of upper-triangular blocks with NB-size column
343 * blocking.
344 *
345 * Loop over the column blocks of size NB of the array A(1:M,1:N)
346 * and the array T(1:NB,1:N), JB is the column index of a column
347 * block, JNB is the column block size at each step JB.
348 *
349  nplusone = n + 1
350  DO jb = 1, n, nb
351 *
352 * (2-0) Determine the column block size JNB.
353 *
354  jnb = min( nplusone-jb, nb )
355 *
356 * (2-1) Copy the upper-triangular part of the current JNB-by-JNB
357 * diagonal block U(JB) (of the N-by-N matrix U) stored
358 * in A(JB:JB+JNB-1,JB:JB+JNB-1) into the upper-triangular part
359 * of the current JNB-by-JNB block T(1:JNB,JB:JB+JNB-1)
360 * column-by-column, total JNB*(JNB+1)/2 elements.
361 *
362  jbtemp1 = jb - 1
363  DO j = jb, jb+jnb-1
364  CALL scopy( j-jbtemp1, a( jb, j ), 1, t( 1, j ), 1 )
365  END DO
366 *
367 * (2-2) Perform on the upper-triangular part of the current
368 * JNB-by-JNB diagonal block U(JB) (of the N-by-N matrix U) stored
369 * in T(1:JNB,JB:JB+JNB-1) the following operation in place:
370 * (-1)*U(JB)*S(JB), i.e the result will be stored in the upper-
371 * triangular part of T(1:JNB,JB:JB+JNB-1). This multiplication
372 * of the JNB-by-JNB diagonal block U(JB) by the JNB-by-JNB
373 * diagonal block S(JB) of the N-by-N sign matrix S from the
374 * right means changing the sign of each J-th column of the block
375 * U(JB) according to the sign of the diagonal element of the block
376 * S(JB), i.e. S(J,J) that is stored in the array element D(J).
377 *
378  DO j = jb, jb+jnb-1
379  IF( d( j ).EQ.one ) THEN
380  CALL sscal( j-jbtemp1, -one, t( 1, j ), 1 )
381  END IF
382  END DO
383 *
384 * (2-3) Perform the triangular solve for the current block
385 * matrix X(JB):
386 *
387 * X(JB) * (A(JB)**T) = B(JB), where:
388 *
389 * A(JB)**T is a JNB-by-JNB unit upper-triangular
390 * coefficient block, and A(JB)=V1(JB), which
391 * is a JNB-by-JNB unit lower-triangular block
392 * stored in A(JB:JB+JNB-1,JB:JB+JNB-1).
393 * The N-by-N matrix V1 is the upper part
394 * of the M-by-N lower-trapezoidal matrix V
395 * stored in A(1:M,1:N);
396 *
397 * B(JB) is a JNB-by-JNB upper-triangular right-hand
398 * side block, B(JB) = (-1)*U(JB)*S(JB), and
399 * B(JB) is stored in T(1:JNB,JB:JB+JNB-1);
400 *
401 * X(JB) is a JNB-by-JNB upper-triangular solution
402 * block, X(JB) is the upper-triangular block
403 * reflector T(JB), and X(JB) is stored
404 * in T(1:JNB,JB:JB+JNB-1).
405 *
406 * In other words, we perform the triangular solve for the
407 * upper-triangular block T(JB):
408 *
409 * T(JB) * (V1(JB)**T) = (-1)*U(JB)*S(JB).
410 *
411 * Even though the blocks X(JB) and B(JB) are upper-
412 * triangular, the routine STRSM will access all JNB**2
413 * elements of the square T(1:JNB,JB:JB+JNB-1). Therefore,
414 * we need to set to zero the elements of the block
415 * T(1:JNB,JB:JB+JNB-1) below the diagonal before the call
416 * to STRSM.
417 *
418 * (2-3a) Set the elements to zero.
419 *
420  jbtemp2 = jb - 2
421  DO j = jb, jb+jnb-2
422  DO i = j-jbtemp2, nb
423  t( i, j ) = zero
424  END DO
425  END DO
426 *
427 * (2-3b) Perform the triangular solve.
428 *
429  CALL strsm( 'R', 'L', 'T', 'U', jnb, jnb, one,
430  $ a( jb, jb ), lda, t( 1, jb ), ldt )
431 *
432  END DO
433 *
434  RETURN
435 *
436 * End of SORHR_COL
437 *
subroutine xerbla(SRNAME, INFO)
XERBLA
Definition: xerbla.f:60
subroutine slaorhr_col_getrfnp(M, N, A, LDA, D, INFO)
SLAORHR_COL_GETRFNP
subroutine scopy(N, SX, INCX, SY, INCY)
SCOPY
Definition: scopy.f:82
subroutine sscal(N, SA, SX, INCX)
SSCAL
Definition: sscal.f:79
subroutine strsm(SIDE, UPLO, TRANSA, DIAG, M, N, ALPHA, A, LDA, B, LDB)
STRSM
Definition: strsm.f:181
Here is the call graph for this function:
Here is the caller graph for this function: