Modify

Ticket #4024 (closed Patches: fixed)

Opened 4 years ago

Last modified 19 months ago

improve performance of inplace_solve

Reported by: guwi17 Owned by: guwi17
Milestone: Boost 1.52.0 Component: uBLAS
Version: Boost 1.42.0 Severity: Optimization
Keywords: performance, triangular solve, inplace solve Cc: consulting@…

Description

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

Attachments

patch_and_test.tgz Download (2.6 KB) - added by guwi17 4 years ago.
patch provided by Jörn
test_inplace_solve.cc Download (3.9 KB) - added by j.ungermann@… 4 years ago.
Test case for inplace solve.

Change History

Changed 4 years ago by guwi17

patch provided by Jörn

Changed 4 years ago by j.ungermann@…

Test case for inplace solve.

comment:1 Changed 4 years ago by j.ungermann@…

Hello, I uploaded a testcase for inplace_solve. It doesn't compile with the current trunk (as it is buggy), but with my patched version. It uses the macros defined in utils.hpp. Compilation time is quite high, execution time is quite fast. It tests all matrix types with both majorities that I am aware of.

I just saw that the line #include <boost/numeric/ublas/triangular.hpp.new> should be #include <boost/numeric/ublas/triangular.hpp> .

comment:2 Changed 4 years ago by consulting@…

  • Cc consulting@… added

comment:3 Changed 20 months ago by guwi17

(In [80267]) boost/numeric/ublas/triangular.hpp - applied patch, see #4024 libs/numeric/ublas/test/test_inplace_solve.cpp - fixed includes

libs/numeric/ublas/test/utils.hpp - applied patch (after s/BOOST_UBLA_TEST/BOOST_UBLAS_TEST/g), see #7296

comment:4 Changed 20 months ago by guwi17

(In [80399]) libs/numeric/ublas/test/test_inplace_solve.cpp: see #4024 - remove unused headers

comment:5 Changed 20 months ago by guwi17

(In [80403]) boost/numeric/ublas/matrix_sparse.hpp : fix mapped_vector_of_mapped_vector

libs/numeric/ublas/test/test_inplace_solve.cpp : make test set configurable, see #4024

libs/numeric/ublas/test/test32.cpp, libs/numeric/ublas/test/test33.cpp : add mapped_vector_of_mapped_vector

libs/numeric/ublas/test/Jamfile.v2 : see #4024 - split some tests to separate "good" and "bad" matrix types

comment:6 Changed 19 months ago by guwi17

comment:7 Changed 19 months ago by guwi17

(In [80590])

comment:8 Changed 19 months ago by guwi17

(In [80599])

  • libs/numeric/ublas/test/test_triangular.cpp - remove unused includes, see #4024

comment:9 Changed 19 months ago by guwi17

  • Owner changed from david.bellot to guwi17
  • Status changed from new to assigned
  • Milestone changed from Boost 1.43.0 to Boost 1.52.0

comment:10 Changed 19 months ago by guwi17

  • Status changed from assigned to closed
  • Resolution set to fixed

(In [80645]) merged [80483],[80487],[80586],[80591],[80592],[80599],[80600],[80624],[80625],[80643],[80644] into release:

  • fix #7296 (hopefully ;-)
  • see #7363 (must wait for a full test cycle before closing this task)
View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
The resolution will be deleted. Next status will be 'reopened'
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.