[Octave-bug-tracker] [bug #57033] Replace CXSPARSE with SPQR

[Rik]

URL:
  <https://savannah.gnu.org/bugs/?57033>

                 Summary: Replace CXSPARSE with SPQR
                 Project: GNU Octave
            Submitted by: rik5
            Submitted on: Thu 10 Oct 2019 09:57:19 AM PDT
                Category: Libraries
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Feature Request
                  Status: Patch Submitted
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
         Discussion Lock: Any
                 Release: dev
        Operating System: Any

    _______________________________________________________

Details:


I appended a test patch and a zip file. The zip file contains the script
test_spqr.m with test cases.  Two test cases use SuiteSparse test matrices in
Matrix Market Format. So I added the test matrices and MatrixMarketUtils to
the zip file. I hope the patch will work on your system.  

The current status of the patch is
1) QR factorization can be calculated for sparse (real|complex) matrices.
2) least square and min2norm solutions can be calculated for sparse
(real|complex) matrices.

Remarks
1) I will improve code formatting. I didn't apply the GNU coding standards
consistently. 
2) Probably the error handling and validation of parameters can be improved.
3) The solve methods for least square and min2norm are moved from class
sparse_qr_rep to class sparse_qr. I can change this if necessary.
4) Macros HAVE_SUITESPARSE_SPQR_H and HAVE_SPQR are defined in oct-sparse.h. I
don't know how to put them into config.h.
5) I didn't do any tests on Windows or Mac.
6) SPQR stores the results of the QR factorization either in a collection of
data structures (H, R, HPinv, HTau) or in one "big" structure of type
SuiteSparseQR_factorization. Unfortunately, there is no user-callable SPQR
function to extract H, R, HPinv and HTau from a
SuiteSparseQR_factorization-object. At least I didn't find one.

The implementation of the R-,C-,Q- and V-methods in class sparse_qr_rep is
based on H, R, HPinv and HTau (calculated in the constructor). For the
implementation of the solve methods the function SuiteSparseQR_min2norm is
very convenient. This function uses the SuiteSparseQR_factorization and does
not reuse H, R, HPinv and HTau. So for a matrix A I do one QR factorization in
order to get R, Q etc. and a further factorization to solve Ax = b.

In the old implementation of sparse_qr_rep there was only one QR factorization
in the constructor. The solve methods and the calculation of R, C, Q and V
based on this single factorization. Therefore I think that the old approach is
more efficient than my implementation.

I am thankful for tips or comments how to proceed.

Simon




    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: Thu 10 Oct 2019 09:57:19 AM PDT  Name: test_spqr_20191006.patch  Size:
61KiB   By: rik5

<http://savannah.gnu.org/bugs/download.php?file_id=47640>
-------------------------------------------------------
Date: Thu 10 Oct 2019 09:57:19 AM PDT  Name: test_spqr_20191006.zip  Size:
1MiB   By: rik5

<http://savannah.gnu.org/bugs/download.php?file_id=47641>

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?57033>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/