tree fdfed2355ac5cd51e0437aaf7fc6cda7ff086c16
parent 8ae054ad91ae402af94f82e4d4ef24957188233b
author Sameer Agarwal <sameeragarwal@google.com> 1643223648 -0800
committer Sameer Agarwal <sameeragarwal@google.com> 1644263641 -0800

Add DenseQR Interface

1. Add EigenDenseQR & tests.
   This implementation now uses an in place decomposition,
   which means that we are not allocating, deallocating
   memory every call.
2. Add LAPACKDenseQR and tests.
   The LAPACK implementation instead of using dgels which is a
   routine which does the factorization and solve in one
   call, now uses dgeqrf for factorization and then
   dormqr and dtrtrs for solving. This allows us to
   have a factorize and solve interface like DenseCholesky.
   And opens the door to iterative refinement and mixed
   precision solves.
3. The refactor also allows us to simplify the interface to
   DenseSparseMatrix considerably. The internals of this
   class were complicated because we had the AppendDiagonal
   and RemoveDiagonal methods and we did not want to allocate
   deallocate memory every call. But since we pay the cost
   of the copy anyways, we can just hold that buffer
   in DenseQRSolver.
4. Delete lapack.cc/h
5. The net result is that everything seems to be a bit faster.
   For LAPACK we are not doing some of the scaling work that
   dgels was doing. For Eigen I think it maybe the inplace
   decomposition.

Benchmark                                                                     Time             CPU      Time Old      Time New       CPU Old       CPU New
----------------------------------------------------------------------------------------------------------------------------------------------------------
BM_DenseSolver<ceres::EIGEN, ceres::DENSE_QR>/1/1                          -0.1154         -0.1159           692           612           691           611
BM_DenseSolver<ceres::EIGEN, ceres::DENSE_QR>/2/1                          -0.1601         -0.1553           717           603           712           601
BM_DenseSolver<ceres::EIGEN, ceres::DENSE_QR>/3/1                          -0.1673         -0.1575           733           610           724           610
BM_DenseSolver<ceres::EIGEN, ceres::DENSE_QR>/6/2                          -0.1008         -0.1003           886           797           884           796
BM_DenseSolver<ceres::EIGEN, ceres::DENSE_QR>/10/3                         -0.1489         -0.1514          1283          1092          1281          1087
BM_DenseSolver<ceres::EIGEN, ceres::DENSE_QR>/12/4                         -0.1040         -0.1104          1556          1394          1553          1381
BM_DenseSolver<ceres::EIGEN, ceres::DENSE_QR>/20/5                         -0.0007         -0.0097          1911          1910          1908          1890
BM_DenseSolver<ceres::EIGEN, ceres::DENSE_QR>/40/5                         -0.1033         -0.1022          2981          2673          2957          2655
BM_DenseSolver<ceres::EIGEN, ceres::DENSE_QR>/100/10                       -0.0147         +0.0015          9275          9138          9026          9040
BM_DenseSolver<ceres::EIGEN, ceres::DENSE_QR>/200/10                       -0.1408         -0.1284         15093         12968         14778         12880
BM_DenseSolver<ceres::EIGEN, ceres::DENSE_QR>/200/20                       -0.0310         -0.0355         38973         37765         38837         37460
BM_DenseSolver<ceres::LAPACK, ceres::DENSE_QR>/1/1                         -0.1228         -0.1256           736           646           731           640
BM_DenseSolver<ceres::LAPACK, ceres::DENSE_QR>/2/1                         -0.1401         -0.1396           740           636           735           633
BM_DenseSolver<ceres::LAPACK, ceres::DENSE_QR>/3/1                         -0.1731         -0.1695           744           615           738           613
BM_DenseSolver<ceres::LAPACK, ceres::DENSE_QR>/6/2                         -0.1399         -0.1408          1121           965          1113           956
BM_DenseSolver<ceres::LAPACK, ceres::DENSE_QR>/10/3                        -0.1110         -0.1145          1571          1397          1560          1382
BM_DenseSolver<ceres::LAPACK, ceres::DENSE_QR>/12/4                        -0.1411         -0.1417          2006          1722          1993          1710
BM_DenseSolver<ceres::LAPACK, ceres::DENSE_QR>/20/5                        -0.1740         -0.1729          2741          2264          2724          2253
BM_DenseSolver<ceres::LAPACK, ceres::DENSE_QR>/40/5                        -0.0966         -0.1123          3462          3128          3425          3040
BM_DenseSolver<ceres::LAPACK, ceres::DENSE_QR>/100/10                      -0.0387         -0.0998         10365          9964         10339          9307
BM_DenseSolver<ceres::LAPACK, ceres::DENSE_QR>/200/10                      -0.2044         -0.2049         16031         12754         15998         12720
BM_DenseSolver<ceres::LAPACK, ceres::DENSE_QR>/200/20                      -0.2391         -0.2386         35777         27223         35716         27193

Change-Id: I782f0d7664efe1435eebda92ddf47a0fe66c9c72