Sparsity pattern matrix format #349

pratikvn · 2019-09-12T16:29:54Z

This PR adds the new sparsity pattern matrix format.

Adds the class definition and the core module.
Adds the core tests.

The main storage is in CSR as the main aim is to use it as an adjacency matrix. Therefore, it ~~does not have a values array~~ has a value array of length one which stores (ValueType)(1.0) by default but a value can be passed in by the user. It has a row_ptrs array and a col_idxs array similar to CSR. The read method ~~disregards the values array~~ reads in the user entered value(1.0 if not entered) and the write method writes the value in the matrix to the MatrixData tuple.

This matrix also has a method which will return the adjacency matrix from the sparsity pattern (which is mostly the removal of the diagonal elements) to satisfy the adjacency matrix requirements. This adjacency matrix has to be square

The motivation behind this matrix format is to be able to represent sparse matrix as graphs so that they can be reordered/partitioned etc.

TODO:

Add the adjacency matrix creation (removal of diagonal elements)

yhmtsai

also need to add the test in test_install.cpp

omp/CMakeLists.txt

cuda/CMakeLists.txt

core/test/matrix/CMakeLists.txt

reference/CMakeLists.txt

core/CMakeLists.txt

core/matrix/sparsity.cpp

include/ginkgo/core/matrix/sparsity.hpp

hartwiganzt · 2019-09-19T09:48:38Z

I may have a few comments here.

Wouldn't it be more flexible to have the possibility to set the (uniform) matrix value? E.g., say "al values are "-1" (which can than be used as part of a stencil matrix) or "all values are 1/nnz"
Can you convert this matrix from/to standard CSR? From CSR you would loose all values (except one), converting to would set all values to the uniform value.

pratikvn · 2019-09-19T10:18:57Z

Wouldn't it be more flexible to have the possibility to set the (uniform) matrix value? E.g., say "al values are "-1" (which can than be used as part of a stencil matrix) or "all values are 1/nnz"

Yes, I can do that. That is a good idea.

Can you convert this matrix from/to standard CSR? From CSR you would loose all values (except one), converting to would set all values to the uniform value.

Yes, it is possible to convert any matrix to this matrix format. Currently, it replaces the values with (ValueType)1.0, but that can be changed. The PR #350 adds that conversion from Dense and CSR. Converting from the sparsity pattern to a CSR, I am not sure if that would be useful, but it is also certainly possible, but not implemented currently(I mean in #350 ).

core/device_hooks/common_kernels.inc.cpp

include/ginkgo/core/matrix/sparsity.hpp

codecov · 2019-09-20T10:42:24Z

Codecov Report

Merging #349 into develop will decrease coverage by 0.33%.
The diff coverage is 69.12%.

@@             Coverage Diff             @@
##           develop     #349      +/-   ##
===========================================
- Coverage    98.29%   97.96%   -0.34%     
===========================================
  Files          251      256       +5     
  Lines        18755    18972     +217     
===========================================
+ Hits         18436    18586     +150     
- Misses         319      386      +67

Impacted Files	Coverage Δ
core/test/utils/matrix_generator.hpp	`100% <ø> (ø)`	⬆️
reference/matrix/sparsity_kernels.cpp	`0% <0%> (ø)`
omp/matrix/sparsity_kernels.cpp	`0% <0%> (ø)`
core/test/matrix/sparsity.cpp	`100% <100%> (ø)`
include/ginkgo/core/matrix/sparsity.hpp	`100% <100%> (ø)`
core/matrix/sparsity.cpp	`45.83% <45.83%> (ø)`
... and 1 more

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update cde698f...46b8000. Read the comment docs.

core/matrix/sparsity.cpp

include/ginkgo/core/matrix/sparsity.hpp

tcojean

Some small changes.

core/matrix/sparsity.cpp

core/test/matrix/sparsity.cpp

core/test/utils/matrix_generator.hpp

include/ginkgo/core/matrix/sparsity.hpp

core/test/matrix/sparsity.cpp

include/ginkgo/core/matrix/sparsity.hpp

+ Add the class definition and core files. + Add the core tests.

yhmtsai

LGTM

pratikvn · 2019-09-24T14:53:09Z

Just a note: The coverage is low because this PR does not implement any kernels and hence none of the that code is covered. The kernels are added in PR #350 and tests for them are added there as well.

thoasm

Looks good, very minor comments

include/ginkgo/core/matrix/sparsity.hpp

core/matrix/sparsity.cpp

thoasm

Missing tests

core/test/matrix/sparsity.cpp

include/ginkgo/core/matrix/sparsity.hpp

+ Add tests for non-const getters.

thoasm

LGTM!

core/test/matrix/sparsity.cpp

The Ginkgo team is proud to announce the new minor release of Ginkgo version 1.1.0. This release brings several performance improvements, adds Windows support, adds support for factorizations inside Ginkgo and a new ILU preconditioner based on ParILU algorithm, among other things. For detailed information, check the respective issue. Supported systems and requirements: + For all platforms, cmake 3.9+ + Linux and MacOS + gcc: 5.3+, 6.3+, 7.3+, 8.1+ + clang: 3.9+ + Intel compiler: 2017+ + Apple LLVM: 8.0+ + CUDA module: CUDA 9.0+ + Windows + MinGW and CygWin: gcc 5.3+, 6.3+, 7.3+, 8.1+ + Microsoft Visual Studio: VS 2017 15.7+ + CUDA module: CUDA 9.0+, Microsoft Visual Studio + OpenMP module: MinGW or CygWin. The current known issues can be found in the [known issues page](https://github.com/ginkgo-project/ginkgo/wiki/Known-Issues). Additions: + Upper and lower triangular solvers ([#327](#327), [#336](#336), [#341](#341), [#342](#342)) + New factorization support in Ginkgo, and addition of the ParILU algorithm ([#305](#305), [#315](#315), [#319](#319), [#324](#324)) + New ILU preconditioner ([#348](#348), [#353](#353)) + Windows MinGW and Cygwin support ([#347](#347)) + Windows Visual studio support ([#351](#351)) + New example showing how to use ParILU as a preconditioner ([#358](#358)) + New example on using loggers for debugging ([#360](#360)) + Add two new 9pt and 27pt stencil examples ([#300](#300), [#306](#306)) + Allow benchmarking CuSPARSE spmv formats through Ginkgo's benchmarks ([#303](#303)) + New benchmark for sparse matrix format conversions ([#312](#312)) + Add conversions between CSR and Hybrid formats ([#302](#302), [#310](#310)) + Support for sorting rows in the CSR format by column idices ([#322](#322)) + Addition of a CUDA COO SpMM kernel for improved performance ([#345](#345)) + Addition of a LinOp to handle perturbations of the form (identity + scalar * basis * projector) ([#334](#334)) + New sparsity matrix representation format with Reference and OpenMP kernels ([#349](#349), [#350](#350)) Fixes: + Accelerate GMRES solver for CUDA executor ([#363](#363)) + Fix BiCGSTAB solver convergence ([#359](#359)) + Fix CGS logging by reporting the residual for every sub iteration ([#328](#328)) + Fix CSR,Dense->Sellp conversion's memory access violation ([#295](#295)) + Accelerate CSR->Ell,Hybrid conversions on CUDA ([#313](#313), [#318](#318)) + Fixed slowdown of COO SpMV on OpenMP ([#340](#340)) + Fix gcc 6.4.0 internal compiler error ([#316](#316)) + Fix compilation issue on Apple clang++ 10 ([#322](#322)) + Make Ginkgo able to compile on Intel 2017 and above ([#337](#337)) + Make the benchmarks spmv/solver use the same matrix formats ([#366](#366)) + Fix self-written isfinite function ([#348](#348)) + Fix Jacobi issues shown by cuda-memcheck Tools and ecosystem: + Multiple improvements to the CI system and tools ([#296](#296), [#311](#311), [#365](#365)) + Multiple improvements to the Ginkgo containers ([#328](#328), [#361](#361)) + Add sonarqube analysis to Ginkgo ([#304](#304), [#308](#308), [#309](#309)) + Add clang-tidy and iwyu support to Ginkgo ([#298](#298)) + Improve Ginkgo's support of xSDK M12 policy by adding the `TPL_` arguments to CMake ([#300](#300)) + Add support for the xSDK R7 policy ([#325](#325)) + Fix examples in html documentation ([#367](#367))

The Ginkgo team is proud to announce the new minor release of Ginkgo version 1.1.0. This release brings several performance improvements, adds Windows support, adds support for factorizations inside Ginkgo and a new ILU preconditioner based on ParILU algorithm, among other things. For detailed information, check the respective issue. Supported systems and requirements: + For all platforms, cmake 3.9+ + Linux and MacOS + gcc: 5.3+, 6.3+, 7.3+, 8.1+ + clang: 3.9+ + Intel compiler: 2017+ + Apple LLVM: 8.0+ + CUDA module: CUDA 9.0+ + Windows + MinGW and Cygwin: gcc 5.3+, 6.3+, 7.3+, 8.1+ + Microsoft Visual Studio: VS 2017 15.7+ + CUDA module: CUDA 9.0+, Microsoft Visual Studio + OpenMP module: MinGW or Cygwin. The current known issues can be found in the [known issues page](https://github.com/ginkgo-project/ginkgo/wiki/Known-Issues). ### Additions + Upper and lower triangular solvers ([#327](#327), [#336](#336), [#341](#341), [#342](#342)) + New factorization support in Ginkgo, and addition of the ParILU algorithm ([#305](#305), [#315](#315), [#319](#319), [#324](#324)) + New ILU preconditioner ([#348](#348), [#353](#353)) + Windows MinGW and Cygwin support ([#347](#347)) + Windows Visual Studio support ([#351](#351)) + New example showing how to use ParILU as a preconditioner ([#358](#358)) + New example on using loggers for debugging ([#360](#360)) + Add two new 9pt and 27pt stencil examples ([#300](#300), [#306](#306)) + Allow benchmarking CuSPARSE spmv formats through Ginkgo's benchmarks ([#303](#303)) + New benchmark for sparse matrix format conversions ([#312](#312)) + Add conversions between CSR and Hybrid formats ([#302](#302), [#310](#310)) + Support for sorting rows in the CSR format by column idices ([#322](#322)) + Addition of a CUDA COO SpMM kernel for improved performance ([#345](#345)) + Addition of a LinOp to handle perturbations of the form (identity + scalar * basis * projector) ([#334](#334)) + New sparsity matrix representation format with Reference and OpenMP kernels ([#349](#349), [#350](#350)) ### Fixes + Accelerate GMRES solver for CUDA executor ([#363](#363)) + Fix BiCGSTAB solver convergence ([#359](#359)) + Fix CGS logging by reporting the residual for every sub iteration ([#328](#328)) + Fix CSR,Dense->Sellp conversion's memory access violation ([#295](#295)) + Accelerate CSR->Ell,Hybrid conversions on CUDA ([#313](#313), [#318](#318)) + Fixed slowdown of COO SpMV on OpenMP ([#340](#340)) + Fix gcc 6.4.0 internal compiler error ([#316](#316)) + Fix compilation issue on Apple clang++ 10 ([#322](#322)) + Make Ginkgo able to compile on Intel 2017 and above ([#337](#337)) + Make the benchmarks spmv/solver use the same matrix formats ([#366](#366)) + Fix self-written isfinite function ([#348](#348)) + Fix Jacobi issues shown by cuda-memcheck ### Tools and ecosystem improvements + Multiple improvements to the CI system and tools ([#296](#296), [#311](#311), [#365](#365)) + Multiple improvements to the Ginkgo containers ([#328](#328), [#361](#361)) + Add sonarqube analysis to Ginkgo ([#304](#304), [#308](#308), [#309](#309)) + Add clang-tidy and iwyu support to Ginkgo ([#298](#298)) + Improve Ginkgo's support of xSDK M12 policy by adding the `TPL_` arguments to CMake ([#300](#300)) + Add support for the xSDK R7 policy ([#325](#325)) + Fix examples in html documentation ([#367](#367)) Related PR: #370

pratikvn added is:new-feature A request or implementation of a feature that does not exist yet. mod:core This is related to the core module. type:matrix-format This is related to the Matrix formats 1:ST:WIP This PR is a work in progress. Not ready for review. labels Sep 12, 2019

pratikvn self-assigned this Sep 12, 2019

pratikvn force-pushed the adjacency-matrix-format branch from e99fabc to 0e0eaa2 Compare September 12, 2019 16:34

pratikvn added 1:ST:ready-for-review This PR is ready for review and removed 1:ST:WIP This PR is a work in progress. Not ready for review. labels Sep 12, 2019

pratikvn requested review from thoasm, yhmtsai, hartwiganzt and tcojean September 12, 2019 16:59

pratikvn changed the title ~~New sparsity pattern matrix format~~ Sparsity pattern matrix format Sep 12, 2019

pratikvn mentioned this pull request Sep 12, 2019

Sparsity format Reference and OpenMP kernels #350

Merged

1 task

pratikvn force-pushed the adjacency-matrix-format branch from e3c81cd to 4ad9724 Compare September 13, 2019 14:14

pratikvn mentioned this pull request Sep 17, 2019

Add a new permutation matrix format #352

Merged

2 tasks

yhmtsai requested changes Sep 18, 2019

View reviewed changes

pratikvn force-pushed the adjacency-matrix-format branch 2 times, most recently from 7884b22 to 8877743 Compare September 18, 2019 21:31

yhmtsai requested changes Sep 20, 2019

View reviewed changes

core/device_hooks/common_kernels.inc.cpp Show resolved Hide resolved

include/ginkgo/core/matrix/sparsity.hpp Show resolved Hide resolved

pratikvn force-pushed the adjacency-matrix-format branch 2 times, most recently from 968db76 to 8fa4529 Compare September 20, 2019 14:49

yhmtsai requested changes Sep 23, 2019

View reviewed changes

core/matrix/sparsity.cpp Show resolved Hide resolved

include/ginkgo/core/matrix/sparsity.hpp Show resolved Hide resolved

tcojean requested changes Sep 23, 2019

View reviewed changes

pratikvn added 3 commits September 23, 2019 23:04

Add a framework for the new sparsity matrix format.

6df1995

+ Add the class definition and core files. + Add the core tests.

Add the adjacency matrix creation to the sparsity pattern format.

89034cf

Review update: doc, formatting, add a common value, diag count kernel.

c7a1456

Review update: Improve constructors, doc and formatting.

4b57eab

pratikvn force-pushed the adjacency-matrix-format branch from e93d5ea to 4b57eab Compare September 23, 2019 21:12

yhmtsai approved these changes Sep 24, 2019

View reviewed changes

thoasm reviewed Sep 24, 2019

View reviewed changes

include/ginkgo/core/matrix/sparsity.hpp Outdated Show resolved Hide resolved

include/ginkgo/core/matrix/sparsity.hpp Outdated Show resolved Hide resolved

include/ginkgo/core/matrix/sparsity.hpp Outdated Show resolved Hide resolved

core/matrix/sparsity.cpp Show resolved Hide resolved

pratikvn force-pushed the adjacency-matrix-format branch 2 times, most recently from ad16d23 to a66d628 Compare September 25, 2019 09:07

thoasm requested changes Sep 26, 2019

View reviewed changes

core/test/matrix/sparsity.cpp Show resolved Hide resolved

core/test/matrix/sparsity.cpp Show resolved Hide resolved

pratikvn force-pushed the adjacency-matrix-format branch from a66d628 to 51aab1b Compare September 26, 2019 09:59

thoasm reviewed Sep 26, 2019

View reviewed changes

include/ginkgo/core/matrix/sparsity.hpp Show resolved Hide resolved

Review update.

46b8000

+ Add tests for non-const getters.

pratikvn force-pushed the adjacency-matrix-format branch from 51aab1b to 46b8000 Compare September 26, 2019 12:54

thoasm approved these changes Sep 27, 2019

View reviewed changes

core/test/matrix/sparsity.cpp Show resolved Hide resolved

tcojean approved these changes Sep 27, 2019

View reviewed changes

pratikvn merged commit 3dd594a into develop Sep 27, 2019

pratikvn deleted the adjacency-matrix-format branch September 27, 2019 13:20

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Sparsity pattern matrix format #349

Sparsity pattern matrix format #349

pratikvn commented Sep 12, 2019 •

edited

Loading

yhmtsai left a comment

hartwiganzt commented Sep 19, 2019

pratikvn commented Sep 19, 2019

codecov bot commented Sep 20, 2019 •

edited

Loading

tcojean left a comment

yhmtsai left a comment

pratikvn commented Sep 24, 2019

thoasm left a comment

thoasm left a comment

thoasm left a comment

Sparsity pattern matrix format #349

Sparsity pattern matrix format #349

Conversation

pratikvn commented Sep 12, 2019 • edited Loading

TODO:

yhmtsai left a comment

Choose a reason for hiding this comment

hartwiganzt commented Sep 19, 2019

pratikvn commented Sep 19, 2019

codecov bot commented Sep 20, 2019 • edited Loading

Codecov Report

tcojean left a comment

Choose a reason for hiding this comment

yhmtsai left a comment

Choose a reason for hiding this comment

pratikvn commented Sep 24, 2019

thoasm left a comment

Choose a reason for hiding this comment

thoasm left a comment

Choose a reason for hiding this comment

thoasm left a comment

Choose a reason for hiding this comment

pratikvn commented Sep 12, 2019 •

edited

Loading

codecov bot commented Sep 20, 2019 •

edited

Loading