#! /usr/bin/env python
#
def svd_solve ( m, n, a, b ):

#*****************************************************************************80
#
## SVD_SOLVE solves a linear system in the least squares sense.
#
#  Discussion:
#
#    The vector X returned by this routine should always minimize the 
#    Euclidean norm of the residual ||A*x-b||.
#
#    If the matrix A does not have full column rank, then there are multiple
#    vectors that attain the minimum residual.  In that case, the vector
#    X returned by this routine is the unique such minimizer that has the 
#    the minimum possible Euclidean norm, that is, ||A*x-b|| and ||x||
#    are both minimized.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    31 August 2016
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    David Kahaner, Cleve Moler, Steven Nash,
#    Numerical Methods and Software,
#    Prentice Hall, 1989,
#    ISBN: 0-13-627258-4,
#    LC: TA345.K34.
#
#  Parameters:
#
#    Input, integer M, the number of rows of A.
#
#    Input, integer N, the number of columns of A.
#
#    Input, real A(M,N), the matrix.
#
#    Input, real B(M), the right hand side.
#
#    Output, real X(N), the least squares solution.
#
  import numpy as np
  from dsvdc import dsvdc
  from sys import exit
#
#  Get the SVD.
#
  a_copy = a
  lda = m
  ldu = m
  ldv = n
  job = 11

  a_copy, sdiag, e, u, v, info = dsvdc ( a_copy, lda, m, n, ldu, ldv, job )

  if ( info != 0 ):
    print ( '' )
    print ( 'SVD_SOLVE - Fatal error!' )
    print ( '  The SVD could not be calculated.' )
    print ( '  LINPACK routine DSVDC returned a nonzero' )
    print ( '  value of the error flag, INFO = %d' % ( info ) )
    exit ( 'SVD_SOLVE - Fatal error!' )

  ub = np.dot ( u.transpose ( ), b )

  sub = np.zeros ( n )
#
#  For singular problems, there may be tiny but nonzero singular values
#  that should be ignored.  This is a reasonable attempt to avoid such 
#  problems, although in general, the user might wish to control the tolerance.
#
  smax = max ( sdiag )
  eps = 2.220446049250313E-016
  if ( smax <= eps ):
    smax = 1.0

  stol = eps * smax

  for i in range ( 0, n ):
    if ( i <= m ):
      if ( stol <= sdiag[i] ):
        sub[i] = ub[i] / sdiag[i]

  x = np.dot ( v, sub )

  return x

def svd_solve_test ( ):

#*****************************************************************************80
#
## SVD_SOLVE_TEST tests SVD_SOLVE.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    31 August 2016
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform
  from r8vec_norm import r8vec_norm
  from test_ls import p00_a
  from test_ls import p00_b
  from test_ls import p00_m
  from test_ls import p00_n
  from test_ls import p00_prob_num
  from test_ls import p00_x

  print ( '' )
  print ( 'SVD_SOLVE_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  SVD_SOLVE is a function with a simple interface which' )
  print ( '  solves a linear system A*x = b in the least squares sense' )
  print ( '  using the singular value decomposition (SVD).' )
  print ( '  Compare a tabulated solution X1 to the QR_SOLVE result X2.' )

  prob_num = p00_prob_num ( )

  print ( '' )
  print ( '  Number of problems = %d' % ( prob_num ) )
  print ( '' )
  print ( '  Index     M     N          ||B||   ||X1 - X2||' ),
  print ( '        ||X1||        ||X2||         ||R1||        ||R2||' )
  print ( '' )

  for prob in range ( 1, prob_num + 1 ):
#
#  Get problem size.
#
    m = p00_m ( prob )
    n = p00_n ( prob )
#
#  Retrieve problem data.
#
    a = p00_a ( prob, m, n )
    b = p00_b ( prob, m )
    x1 = p00_x ( prob, n )

    b_norm = r8vec_norm ( m, b )
    x1_norm = r8vec_norm ( n, x1 )
    r1 = np.dot ( a, x1 ) - b
    r1_norm = r8vec_norm ( m, r1 )
#
#  Use SVD_SOLVE on the problem.
#  Since we want to compute residuals ourselves, we need
#  to keep the originals of A and B, so we make copies
#  to send to SVD_SOLVE.
#
    a_qr = a.copy ( )
    b_qr = b.copy ( )
    x2 = svd_solve ( m, n, a_qr, b_qr )

    x2_norm = r8vec_norm ( n, x2 )
    r2 = np.dot ( a, x2 ) - b
    r2_norm = r8vec_norm ( m, r2 )
#
#  Compare tabulated and computed solutions.
#
    x_diff_norm = r8vec_norm ( n, x1 - x2 )
#
#  Report results for this problem.
#
    print ( '  %5d  %4d  %4d' % ( prob, m, n ) ),
    print ( '  %12.4g  %12.4g' % ( b_norm, x_diff_norm ) ),
    print ( '  %12.4g  %12.4g' % ( x1_norm, x2_norm ) ),
    print ( '  %12.4g  %12.4g' % ( r1_norm, r2_norm ) )
#
#  Terminate.
#
  print ( '' )
  print ( 'SVD_SOLVE_TEST' )
  print ( '  Normal end of execution.' )
  return

if ( __name__ == '__main__' ):
  from timestamp import timestamp
  timestamp ( )
  svd_solve_test ( )
  timestamp ( )