[Boost-bugs] [Boost C++ Libraries] #4024: improve performance of inplace_solve

Subject: [Boost-bugs] [Boost C++ Libraries] #4024: improve performance of inplace_solve
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2010-03-17 20:58:35

#4024: improve performance of inplace_solve
----------------------------------------------------------+-----------------
 Reporter:  guwi17                                        |       Owner:  david.bellot
     Type:  Patches                                       |      Status:  new         
Milestone:  Boost 1.43.0                                  |   Component:  uBLAS       
  Version:  Boost 1.42.0                                  |    Severity:  Optimization
 Keywords:  performance, triangular solve, inplace solve  |  
----------------------------------------------------------+-----------------
 Joern Ungermann proposed a patch to improve performance of inplace_solve.

 The inplace_solve routine has to cope for 24 different cases:

 a) row_major / column_major

 b) upper / lower

 c) dense / packed / sparse

 d) A * x = b / x * A = b

 The case
 row_major / lower_tag / A * x = b is currently mapped to row_major /
 upper_tag / x * A = b
 and the case
 row_major / upper_tag / A * x = b is currently mapped to row_major /
 lower_tag / x * A = b
 This is very inefficient for compressed_matrix types!
 The cases column_major / [lower_tag | upper_tag] / x * A = b are
 seemingly handled, but I can't get it to complile.
 The cases of row_major / [lower_tag | upper_tag] / x * A = b *do* have
 an efficient implementation, which is *not* used to a programming bug,
 i.e. making the choice of the function depending on the storage type of
 the vector and not on the matrix.

 I rewrote triangular.hpp to

 a) handle *all* cases of A * x = b and to

 b) "redirect" the x * A = b cases to the aforementioned ones.

 This keeps the code about the same size as it currently is. It costs
 some efficiently for the redirected cases, but previously certain cases
 were also redirected (just different ones). It is trivial to add the
 missing cases, but adds quite a bit of code.



 {{{
            old (dense) new (dense) old (sparse) new (sparse)
 col_low x: 3240000     3240000     10000        10000
 row_low x: 5100000     3720000     2590000      10000
 col_upp x: 3320000     3340000     10000        10000
 row_upp x: 5120000     3750000     2790000      10000
 x col_low: -           4660000     -            10000
 x row_low: 3330000     4060000     3750000      20000
 x col_upp: -           5110000     -            20000
 x row_upp: 3230000     3910000     3750000      10000

 with dense=ublas::matrix and sparse=ublas::compressed_matrix
 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/4024>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.