8000 Perturbation LinOp by yhmtsai · Pull Request #334 · ginkgo-project/ginkgo · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Perturbation LinOp #334

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 17 commits into from
Aug 23, 2019
Merged

Perturbation LinOp #334

merged 17 commits into from
Aug 23, 2019

Conversation

yhmtsai
Copy link
Member
@yhmtsai yhmtsai commented Aug 12, 2019

Add the LinOp to handle the kind of (I + coef * U * V)
Reflection can be used in householder QR or block QR.
Q of QR can be a form of (I + c1u1u1*) ... (I + ckukuk*) in Householder QR
Q of QR can be a form of (I + WkYk*) ... (I + WkYk*) in block QR
Reflection stores the V explicitly even if V = U*

@yhmtsai yhmtsai changed the title Reflection Reflection LinOp Aug 12, 2019
@pratikvn pratikvn added mod:core This is related to the core module. is:new-feature A request or implementation of a feature that does not exist yet. labels Aug 12, 2019
@hartwiganzt
Copy link
Collaborator

That I understand it right - you want to have a LinOp "Reflection" such that for a matrix A you can generate the reflection matrix R(A) (or short ''R'') and then you can apply the Reflection R to a vector in the form t=R(v).
Is that correct?

@yhmtsai
Copy link
Member Author
yhmtsai commented Aug 12, 2019

@hartwiganzt
Reflection only handles one (I+cUV), so we need to use composition of reflections as Q.
Reflection is like Composition/CSR/.....
Reflection stores the operators, but it does not generate anything from a matrix.
Generating the operators from the matrix should be in QR.

For example,

[u1, u2, ....] = Householder_QR(A) // u1 u2 is the householder factors
Qi = Reflection(-2, u1) // householder matrix Q = (I-2uu*)
Q = Q1* x Q2* x Qn* // composition of reflection. do not form it explictly.

@codecov
Copy link
codecov bot commented Aug 12, 2019

Codecov Report

Merging #334 into develop will increase coverage by 0.03%.
The diff coverage is 93.65%.

Impacted file tree graph

@@             Coverage Diff             @@
##           develop     #334      +/-   ##
===========================================
+ Coverage    88.26%   88.29%   +0.03%     
===========================================
  Files          250      254       +4     
  Lines        19552    19678     +126     
===========================================
+ Hits         17257    17375     +118     
- Misses        2295     2303       +8
Impacted Files Coverage Δ
core/base/reflection.cpp 100% <100%> (ø)
reference/test/base/reflection.cpp 100% <100%> (ø)
core/test/base/reflection.cpp 86.66% <86.66%> (ø)
include/ginkgo/core/base/reflection.hpp 92% <92%> (ø)

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 cd7465d...3225206. Read the comment docs.

@codecov
Copy link
codecov bot commented Aug 12, 2019 •
edited
Loading

Codecov Report

Merging #334 into develop will decrease coverage by 0.03%.
The diff coverage is 94.28%.

Impacted file tree graph

@@             Coverage Diff             @@
##           develop     #334      +/-   ##
===========================================
- Coverage    98.25%   98.22%   -0.04%     
===========================================
  Files          233      237       +4     
  Lines        17855    17993     +138     
===========================================
+ Hits         17543    17673     +130     
- Misses         312      320       +8
Impacted Files Coverage Δ
include/ginkgo/core/base/composition.hpp 93.33% <100%> (ø) ⬆️
core/base/perturbation.cpp 100% <100%> (ø)
include/ginkgo/core/base/combination.hpp 90.9% <100%> (ø) ⬆️
reference/test/base/perturbation.cpp 100% <100%> (ø)
core/test/base/perturbation.cpp 87.23% <87.23%> (ø)
include/ginkgo/core/base/perturbation.hpp 94.44% <94.44%> (ø)

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 93763f2...3cdc4b6. Read the comment docs.

pratikvn
pratikvn requested changes Aug 13, 2019
View reviewed changes
Copy link
Member
@pratikvn pratikvn left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Some generic comments.. mainly regarding documentation

include/ginkgo/core/base/reflection.hpp Outdated
*
* @tparam ValueType precision of input and result vectors
*
* @ingroup LinOp
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You can also create a new group called Reflection and add it to that, if necessary

@yhmtsai yhmtsai mentioned this pull request Aug 13, 2019
Closed
thoasm
thoasm requested changes Aug 13, 2019
View reviewed changes
Copy link
Member
@thoasm thoasm left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Documentation and guideline comments.

@yhmtsai
Copy link
Member Author
yhmtsai commented Aug 14, 2019

I add the description and change the name.
Currently, (I + coef * U * V) -> (Identity + scalar * basis * projector)

pratikvn
pratikvn approved these changes Aug 14, 2019
View reviewed changes
Copy link
Member
@pratikvn pratikvn left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Minor

thoasm
thoasm requested changes Aug 19, 2019
View reviewed changes
Copy link
Member
@thoasm thoasm left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Mostly remarks about comments, with a suggestion that could improve performance in some cases

@pratikvn pratikvn changed the title Reflection LinOp Perturbation LinOp Aug 19, 2019
@yhmtsai
Copy link
Member Author
yhmtsai commented Aug 20, 2019 •
edited
Loading

sonar report a bug for the commit 7bc7922
cache_struct needs to follow Rules-of-five(destructor, copy constructor, copy-assignment, move constructor, and move-assignment). Do not need to add move operation if there is no fast way.
Reference: https://rules.sonarsource.com/cpp/tag/leak/RSPEC-3624

thoasm
thoasm requested changes Aug 21, 2019
View reviewed changes
Copy link
Member
@thoasm thoasm left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good, just minor comments.

@thoasm
Copy link
Member
thoasm commented Aug 21, 2019

Can somebody check the comments of this PR (maybe also the name choices) if they are fine from a mathematical point of view (I think @hartwiganzt and/or @pratikvn would be good)?

pratikvn
pratikvn approved these changes Aug 22, 2019
View reviewed changes
Copy link
Member
@pratikvn pratikvn left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM! Just some minor cosmetic changes.

include/ginkgo/core/base/perturbation.hpp Outdated
* `(identity + scalar * basis * projector)` This operator adds a movement along
* a direction constructed by `basis` and `projector` on the LinOp. `projector`
* gives the coefficient of `basis` to decide the direction.
* For example, Householder matrix can be represented in Perturbation.
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
* For example, Householder matrix can be represented in Perturbation.
* For example, the Householder matrix can be represented with the Perturbation operator as follows.

include/ginkgo/core/base/perturbation.hpp Outdated
* a direction constructed by `basis` and `projector` on the LinOp. `projector`
* gives the coefficient of `basis` to decide the direction.
* For example, Householder matrix can be represented in Perturbation.
* u is the householder factor and then we can generate the Householder matrix =
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
* u is the householder factor and then we can generate the Householder matrix =
*
* If u is the Householder factor then we can generate the [Householder transformation matrix](https://en.wikipedia.org/wiki/Householder_transformation),

include/ginkgo/core/base/perturbation.hpp Outdated
* gives the coefficient of `basis` to decide the direction.
* For example, Householder matrix can be represented in Perturbation.
* u is the householder factor and then we can generate the Householder matrix =
* (I - 2 u u*). In this case, the parameters of Perturbation class are
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
* (I - 2 u u*). In this case, the parameters of Perturbation class are
* H = (I - 2 u u*). In this case, the parameters of Perturbation class are

include/ginkgo/core/base/perturbation.hpp Outdated

protected:
/**
* Creates an empty operator perturbation (0x0 operator).
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
* Creates an empty operator perturbation (0x0 operator).
* Creates an empty perturbation operator. (0x0 operator).

include/ginkgo/core/base/perturbation.hpp Outdated
LinOp *x) const override;

/**
* validate_perturbation check the dimension of scalar, basis, projector.
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

No need to add the function name like this. I would suggest this:

Suggested change
* validate_perturbation check the dimension of scalar, basis, projector.
* Validates the dimensions of the `scalar`, `basis` and `projector` parameters for the `apply`.

thoasm
thoasm approved these changes Aug 22, 2019
View reviewed changes
Copy link
Member
@thoasm thoasm left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM!

@tcojean tcojean added the 1:ST:ready-to-merge This PR is ready to merge. label Aug 22, 2019
@yhmtsai yhmtsai merged commit 1600c6d into ginkgo-project:develop Aug 23, 2019
tcojean added a commit that referenced this pull request Oct 20, 2019
@tcojean
Merge Release v1.1.0
b9bec82 
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](https://github.com/ginkgo-project/ginkgo/issues/312)[#317](https://github.com/ginkgo-project/ginkgo/issues/317))
+ 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))
tcojean added a commit that referenced this pull request Oct 21, 2019
@tcojean
Merge Release v1.1.0 for develop
20823e7 
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](https://github.com/ginkgo-project/ginkgo/issues/312)[#317](https://github.com/ginkgo-project/ginkgo/issues/317))
+ 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@pratikvn pratikvn pratikvn approved these changes

@thoasm thoasm thoasm approved these changes

@tcojean tcojean Awaiting requested review from tcojean

@hartwiganzt hartwiganzt Awaiting requested review from hartwiganzt

Assignees

@yhmtsai yhmtsai

Labels
1:ST:ready-to-merge This PR is ready to merge. is:new-feature A request or implementation of a feature that does not exist yet. mod:core This is related to the core module.
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
5 participants
@yhmtsai @hartwiganzt @thoasm @pratikvn @tcojean
0