SVD для решения разреженной системы harwell-boeing a.x=b в C/C++?

Кто-нибудь знает разреженный SVD-решатель для С++? Моя проблема связана с некоторыми плохо обусловленными матрицами, которые могут иметь нулевые столбцы/строки. Мои данные хранятся в матрице uBLAS, которая представляет собой разреженный формат Harwell-Boeing.

У меня возникли проблемы с поиском:

Решатель SVD

  1. Решатель SVD, который может работать с разреженными матрицами. Лапак, кажется, не в состоянии сделать это? Я хочу, чтобы разреженные матрицы передавались в функцию и выводились разреженные матрицы.
  2. Способ рекомбинации результатов... Чтобы я мог считать xs из x=b(A^-1). Я ожидаю, что это будет x=(b)(v.(d^-1).(u^t))

Я надеюсь воссоздать следующие два шага из GSL.

gsl_linalg_SV_decomp_jacobi (gsl_matrix * A, gsl_matrix * V, gsl_vector * S) 
gsl_linalg_SV_solve (const gsl_matrix * U, const gsl_matrix * V, const gsl_vector * S, const gsl_vector * b, gsl_vector * x)

Я также понятия не имею, как обернуть библиотеку FORTRAN в С++. Где/есть ли привязки PROPACK c/c++?

Редактировать 1: у меня проблемы с PROPACK. Выводит ли PROPACK разреженные матрицы? Кажется, что V выводится как «V (LDV, KMAX): массив DOUBLE PRECISION». что будет означать, что это не так?


person Mikhail    schedule 05.07.2011    source источник


Ответы (3)


SVDLIBC — это библиотека C с частичная поддержка формата Harwell-Boeing. Я не знаком с библиотекой, но на первый взгляд она соответствует вашим требованиям.

person antonakos    schedule 06.07.2011
comment
Ближе всего к тому, что я хотел. Хотя я не знаю, будет ли это работать! - person Mikhail; 12.07.2011

Вы упомянули PROPACK. Fortran совместим с C, вам просто нужно знать, как работает соглашение о вызовах. Я не уверен, но я думаю, что функция, которую вы хотите вызвать в PROPACK, это dlansvd (предполагая двойную точность), которая задокументирована следующим образом:

  subroutine dlansvd(jobu,jobv,m,n,k,kmax,aprod,U,ldu,Sigma,bnd,
 c     V,ldv,tolin,work,lwork,iwork,liwork,doption,ioption,info,
 c     dparm,iparm)


c     DLANSVD: Compute the leading singular triplets of a large and
c     sparse matrix by Lanczos bidiagonalization with partial
c     reorthogonalization.
c
c     Parameters:
c
c     JOBU: CHARACTER*1. If JOBU.EQ.'Y' then compute the left singular vectors.
c     JOBV: CHARACTER*1. If JOBV.EQ.'Y' then compute the right singular 
c           vectors.
c     M: INTEGER. Number of rows of A.
c     N: INTEGER. Number of columns of A.
c     K: INTEGER. Number of desired singular triplets. K <= MIN(KMAX,M,N)
c     KMAX: INTEGER. Maximal number of iterations = maximal dimension of
c           the generated Krylov subspace.
c     APROD: Subroutine defining the linear operator A. 
c            APROD should be of the form:
c
c           SUBROUTINE DAPROD(TRANSA,M,N,X,Y,DPARM,IPARM)
c           CHARACTER*1 TRANSA
c           INTEGER M,N,IPARM(*)
c           DOUBLE PRECISION X(*),Y(*),DPARM(*)
c
c           If TRANSA.EQ.'N' then the function should compute the matrix-vector
c           product Y = A * X.
c           If TRANSA.EQ.'T' then the function should compute the matrix-vector
c           product Y = A^T * X.
c           The arrays IPARM and DPARM are a means to pass user supplied
c           data to APROD without the use of common blocks.
c     U(LDU,KMAX+1): DOUBLE PRECISION array. On return the first K columns of U
c               will contain approximations to the left singular vectors 
c               corresponding to the K largest singular values of A.
c               On entry the first column of U contains the starting vector
c               for the Lanczos bidiagonalization. A random starting vector
c               is used if U is zero.
c     LDU: INTEGER. Leading dimension of the array U. LDU >= M.
c     SIGMA(K): DOUBLE PRECISION array. On return Sigma contains approximation
c               to the K largest singular values of A.
c     BND(K)  : DOUBLE PRECISION array. Error estimates on the computed 
c               singular values. The computed SIGMA(I) is within BND(I)
c               of a singular value of A.
c     V(LDV,KMAX): DOUBLE PRECISION array. On return the first K columns of V
c               will contain approximations to the right singular vectors 
c               corresponding to the K largest singular values of A.
c     LDV: INTEGER. Leading dimension of the array V. LDV >= N.
c     TOLIN: DOUBLE PRECISION. Desired relative accuracy of computed singular 
c            values. The error of SIGMA(I) is approximately 
c            MAX( 16*EPS*SIGMA(1), TOLIN*SIGMA(I) )
c     WORK(LWORK): DOUBLE PRECISION array. Workspace of dimension LWORK.
c     LWORK: INTEGER. Dimension of WORK.
c            If JOBU.EQ.'N' and JOBV.EQ.'N' then  LWORK should be at least
c            M + N + 9*KMAX + 2*KMAX**2 + 4 + MAX(M+N,4*KMAX+4).
c            If JOBU.EQ.'Y' or JOBV.EQ.'Y' then LWORK should be at least
c            M + N + 9*KMAX + 5*KMAX**2 + 4 + 
c            MAX(3*KMAX**2+4*KMAX+4, NB*MAX(M,N)), where NB>1 is a block 
c            size, which determines how large a fraction of the work in
c            setting up the singular vectors is done using fast BLAS-3 
c            operation. 
c     IWORK: INTEGER array. Integer workspace of dimension LIWORK.
c     LIWORK: INTEGER. Dimension of IWORK. Should be at least 8*KMAX if
c             JOBU.EQ.'Y' or JOBV.EQ.'Y' and at least 2*KMAX+1 otherwise.
c     DOPTION: DOUBLE PRECISION array. Parameters for LANBPRO.
c        doption(1) = delta. Level of orthogonality to maintain among
c          Lanczos vectors.
c        doption(2) = eta. During reorthogonalization, all vectors with
c          with components larger than eta along the latest Lanczos vector
c          will be purged.
c        doption(3) = anorm. Estimate of || A ||.
c     IOPTION: INTEGER array. Parameters for LANBPRO.
c        ioption(1) = CGS.  If CGS.EQ.1 then reorthogonalization is done
c          using iterated classical GRAM-SCHMIDT. IF CGS.EQ.0 then 
c          reorthogonalization is done using iterated modified Gram-Schmidt.
c        ioption(2) = ELR. If ELR.EQ.1 then extended local orthogonality is
c          enforced among u_{k}, u_{k+1} and v_{k} and v_{k+1} respectively.
c     INFO: INTEGER. 
c         INFO = 0  : The K largest singular triplets were computed succesfully
c         INFO = J>0, J<K: An invariant subspace of dimension J was found.
c         INFO = -1 : K singular triplets did not converge within KMAX
c                     iterations.   
c     DPARM: DOUBLE PRECISION array. Array used for passing data to the APROD
c         function.   
c     IPARM: INTEGER array. Array used for passing data to the APROD
c         function.   
c
c     (C) Rasmus Munk Larsen, Stanford, 1999, 2004 
c

Важно помнить, что в Фортране все параметры передаются по ссылке, а неразреженные массивы хранятся в формате столбцов. Таким образом, правильное объявление этой функции в C++ должно быть следующим (не проверено):

extern "C"
void dlansvd(const char *jobu,
             const char *jobv,
             int *m,
             int *n,
             int *k,
             int *kmax,
             void (*aprod)(const char *transa,
                           int *m,
                           int *n,
                           int *iparm,
                           double *x,
                           double *y,
                           double *dparm),
             double *U,
             int *ldu,
             double *Sigma,
             double *bnd,
             double *V,
             int *ldv,
             double *tolin,
             double *work,
             int *lwork,
             int *iwork,
             int *liwork,
             double *doption,
             int *ioption,
             int *info,
             double *dparm,
             int *iparm);

Это настоящий зверь. Удачи!

person Adam Rosenfield    schedule 05.07.2011
comment
В настоящее время я изучаю этот маршрут: хотя это совсем не то направление, в котором я хотел идти :-). Есть небольшая опечатка: должно быть двойное *V, int *ldv... (v не u) - person Mikhail; 05.07.2011
comment
Это выводит плотные (не разреженные) массивы? Есть ли тот, который поддерживает разреженные массивы? Моя матрица A будет иметь ширину не менее 10000x10000+ единиц... - person Mikhail; 05.07.2011

Возможно, стоит проверить разреженное программное обеспечение для линейной алгебры Тима Дэвиса: http://www.cise.ufl.edu/~davis/

Вообще говоря, я нашел его программное обеспечение действительно полезным, как правило, очень эффективным и надежным.

Кажется, он работал над разреженным пакетом СВД со студентом, но я не уверен, на какой стадии находится проект.

Надеюсь это поможет.

person Darren Engwirda    schedule 05.07.2011
comment
@Misha: Если пройти по ссылке на его сайт, то найди текущих студентов и загляни в проект про редкую СВД. Судя по моему очень быстрому просмотру, кажется, что вы сможете получить доступ к коду, если отправите электронное письмо... - person Darren Engwirda; 05.07.2011