ginkgo own ILU and IC #1684

yhmtsai · 2024-09-26T09:22:44Z

This pr enables the ginkgo's implementation ILU through the current LU implementation.
To enable that, we need to allow LU can ignore the missing fill-in entries.
It is controlled by checked_lookup parameter, and user needs to pass the same sparsityCsr as the original one as the symbolic factor to get ILU.
Moreover, this pr also adds a parameter for algorithm selection. It will forward the information to LU and unpack them directly to return the same structure as the original sparselib.
Note. LU by default gives combined matrix but ILU gives the composition.

The first commit shows that the hashmap lookup leads the hang issue and bitmap lookup leads illegal memory access (incorrect result with -1 index return).
The second commit shows the results are wrong if we do not ignore missing fill-in entries update after fixing infinite loop of hashmap lookup

After this pr, we provide another way to factorize ILU without relying on the sparse library.

TODO

cholesky (in this pr, too)

nbeams

I have some questions and comments, but overall I am excited about this! Thanks @yhmtsai

common/cuda_hip/factorization/lu_kernels.cpp

nbeams · 2024-09-26T18:42:26Z

core/factorization/ilu.cpp

+                    local_system_matrix->get_const_row_ptrs())));
+        ilu =
+            gko::experimental::factorization::Lu<ValueType, IndexType>::build()
+                .with_checked_lookup(true)


Same here, would prefer with_safe_lookup or something like that, personally.

IMO this should rather be a new type, LU and ILU(...) have very different use cases. That would also allow us to build a new, improved ILU preconditioner interface based on the Factorization type instead of the slightly hacky Composition-like type ILU is currently.

core/factorization/ilu.cpp

include/ginkgo/core/factorization/ilu.hpp

include/ginkgo/core/factorization/lu.hpp

core/matrix/csr_lookup.hpp

upsj

Thanks Mike, I'm happy to see how simple this was to extend to ILU. Some design and naming suggestions I'd like to see discussed, and maybe we should build a roadmap for the future ILU preconditioner interface.

core/factorization/factorization.cpp

common/cuda_hip/factorization/lu_kernels.cpp

nbeams

A few more minor comments, but most of my questions/issues have been addressed.

include/ginkgo/core/factorization/lu.hpp

core/factorization/lu.cpp

include/ginkgo/core/factorization/cholesky.hpp

include/ginkgo/core/factorization/lu.hpp

nbeams

Looking good, but I have some more minor comments.

include/ginkgo/core/factorization/lu.hpp

core/factorization/ic.cpp

core/factorization/ilu.cpp

include/ginkgo/core/factorization/incompleted_factorization.hpp

reference/test/factorization/lu_kernels.cpp

test/factorization/lu_kernels.cpp

include/ginkgo/core/factorization/incompleted_factorization.hpp

upsj

I'm not 100% convinced it's a good choice to put both ILU and LU into the same gko::kernels::... function (It's fine if they use the same kernel, just the function itself), since the interface to LU will probably change significantly in the future. Otherwise only the suggestion of using if constexpr where it makes sense

common/cuda_hip/factorization/cholesky_kernels.cpp

common/cuda_hip/factorization/lu_kernels.cpp

omp/factorization/cholesky_kernels.cpp

reference/factorization/cholesky_kernels.cpp

reference/factorization/lu_kernels.cpp

yhmtsai · 2024-11-27T14:20:58Z

I don't get the meaning about putting into gko::kernels, I think all kernel functions are in the namespace.
Could you elaborate it more?
I do not think this change give any changes to LU. It only touches ILU interface now.
Also, LU in experimental, although it is not good, we can still change the LU interface.
I would also like to reduce thought on unclear future to stop this pr. There are a few pr hang by that comment, but they are resolved in long time more than one year.

upsj · 2024-11-27T14:33:19Z

instead of adding a new parameter to factorize, forcing me to split that function later on when I implement more LU-specific preprocessing and optimizations, split it into factorize and incomplete_factorize. For now they use the same kernel (and the full_fillin template parameter is fine, since this is limited only to a single file), in the future they will likely not.

dismissing, as it referred to earlier interface issues

upsj

I'll likely have to split up the factorize function into two different kernels without full_fillin very soon, but I won't hold up the PR any further. Thanks for the updates

yhmtsai · 2024-11-28T18:12:57Z

@upsj Yes, that makes sense if these kernels can not share most of part

- bitmap: lead wrong answer or segfault - hashmap: infinite loop

…pposite behavior). Co-authored-by: Tobias Ribizel <[email protected]> Co-authored-by: Natalie Beams <[email protected]>

…rategy" to avoid new strategy input

Co-authored-by: Tobias Ribizel <[email protected]>

Co-authored-by: Natalie Beams <[email protected]>

Co-authored-by: Marcel Koch <[email protected]>

Co-authored-by: Tobias Ribizel <[email protected]>

sonarqubecloud · 2024-11-29T15:18:36Z

Quality Gate failed

Failed conditions
23.2% Duplication on New Code (required ≤ 20%)

See analysis details on SonarQube Cloud

This PR adds ginkgo own impelementation for ILU and IC. It is controlled by `incomplete_algorithm::sync_free`. Related PR: ginkgo-project#1684

yhmtsai added the 1:ST:ready-for-review This PR is ready for review label Sep 26, 2024

yhmtsai requested review from nbeams, upsj and a team September 26, 2024 09:22

yhmtsai self-assigned this Sep 26, 2024

ginkgo-bot added reg:build This is related to the build system. reg:testing This is related to testing. type:matrix-format This is related to the Matrix formats type:factorization This is related to the Factorizations mod:all This touches all Ginkgo modules. labels Sep 26, 2024

yhmtsai marked this pull request as ready for review September 26, 2024 09:23

nbeams reviewed Sep 26, 2024

View reviewed changes

upsj previously requested changes Sep 26, 2024

View reviewed changes

upsj reviewed Sep 30, 2024

View reviewed changes

core/factorization/factorization.cpp Outdated Show resolved Hide resolved

MarcelKoch reviewed Oct 1, 2024

View reviewed changes

common/cuda_hip/factorization/lu_kernels.cpp Outdated Show resolved Hide resolved

yhmtsai force-pushed the gko_ilu branch from abac7cc to a97eb6a Compare October 7, 2024 20:14

MarcelKoch added this to the Ginkgo 1.9.0 milestone Oct 17, 2024

yhmtsai force-pushed the gko_ilu branch from a97eb6a to 452150d Compare October 29, 2024 09:25

yhmtsai requested review from nbeams, upsj and MarcelKoch October 29, 2024 09:25

nbeams reviewed Oct 29, 2024

View reviewed changes

include/ginkgo/core/factorization/lu.hpp Outdated Show resolved Hide resolved

core/factorization/lu.cpp Outdated Show resolved Hide resolved

yhmtsai force-pushed the gko_ilu branch from b3f3eb0 to 4eb5165 Compare November 6, 2024 14:57

upsj reviewed Nov 6, 2024

View reviewed changes

include/ginkgo/core/factorization/cholesky.hpp Outdated Show resolved Hide resolved

include/ginkgo/core/factorization/lu.hpp Outdated Show resolved Hide resolved

yhmtsai changed the title ~~ginkgo ILU~~ ginkgo own ILU and IC Nov 7, 2024

yhmtsai requested review from upsj and nbeams November 12, 2024 18:49

nbeams reviewed Nov 20, 2024

View reviewed changes

yhmtsai force-pushed the gko_ilu branch 2 times, most recently from 990a6ce to 31f0966 Compare November 20, 2024 17:02

yhmtsai force-pushed the gko_ilu branch from d681a82 to 8204f85 Compare November 27, 2024 09:32

upsj reviewed Nov 27, 2024

View reviewed changes

yhmtsai force-pushed the gko_ilu branch from 73fd5a7 to cad475b Compare November 28, 2024 13:34

upsj approved these changes Nov 28, 2024

View reviewed changes

yhmtsai and others added 17 commits November 29, 2024 09:54

add failed test when given symbolic without fillin.

7c1c8f4

- bitmap: lead wrong answer or segfault - hashmap: infinite loop

fix infinite loop of lookup_hash_unsafe and add test in reference

68cb9db

add checked_lookup into LU

df8eab4

add ilu syncfree through lu implementation

8179c0b

update the documentation, change checked_lookup -> has_full_fillin (o…

e7330b1

…pposite behavior). Co-authored-by: Tobias Ribizel <[email protected]> Co-authored-by: Natalie Beams <[email protected]>

use unpack directly from factorization and add unpack with strategy

8d4d85c

remove the duplicated initialization

cbde108

Revert "use unpack directly from factorization and add unpack with st…

d2ee3a3

…rategy" to avoid new strategy input

update documentation

38bc404

cholesky failed test

c258472

move the algorithm enum to another header

8951e72

cholesky with safe lookup, wrap it into Ic, and add some missing tests

7df9746

copy the call from lu/cholesky to ilu/ic and delete full_fillin

29c7ce2

Co-authored-by: Tobias Ribizel <[email protected]>

refine the wording and fix wrong bool value

da98fc2

Co-authored-by: Natalie Beams <[email protected]>

update to incomplete_factorization and throw with omp using sparselib

c28c9a2

fix Ref also considered as Omp executor

cd31504

Co-authored-by: Marcel Koch <[email protected]>

use if constexpr when it is possible and reverse if-else

f1951bb

Co-authored-by: Tobias Ribizel <[email protected]>

yhmtsai force-pushed the gko_ilu branch from cad475b to f1951bb Compare November 29, 2024 08:54

yhmtsai merged commit e848148 into develop Nov 29, 2024
10 of 11 checks passed

yhmtsai deleted the gko_ilu branch November 29, 2024 12:48

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

ginkgo own ILU and IC #1684

ginkgo own ILU and IC #1684

yhmtsai commented Sep 26, 2024 •

edited

Loading

nbeams left a comment

nbeams Sep 26, 2024

upsj Sep 26, 2024

upsj left a comment

nbeams left a comment

nbeams left a comment

upsj left a comment

yhmtsai commented Nov 27, 2024 •

edited

Loading

upsj commented Nov 27, 2024 •

edited

Loading

upsj left a comment

yhmtsai commented Nov 28, 2024

sonarqubecloud bot commented Nov 29, 2024

ginkgo own ILU and IC #1684

ginkgo own ILU and IC #1684

Conversation

yhmtsai commented Sep 26, 2024 • edited Loading

nbeams left a comment

Choose a reason for hiding this comment

nbeams Sep 26, 2024

Choose a reason for hiding this comment

upsj Sep 26, 2024

Choose a reason for hiding this comment

upsj left a comment

Choose a reason for hiding this comment

nbeams left a comment

Choose a reason for hiding this comment

nbeams left a comment

Choose a reason for hiding this comment

upsj left a comment

Choose a reason for hiding this comment

yhmtsai commented Nov 27, 2024 • edited Loading

upsj commented Nov 27, 2024 • edited Loading

upsj left a comment

Choose a reason for hiding this comment

yhmtsai commented Nov 28, 2024

sonarqubecloud bot commented Nov 29, 2024

Quality Gate failed

yhmtsai commented Sep 26, 2024 •

edited

Loading

yhmtsai commented Nov 27, 2024 •

edited

Loading

upsj commented Nov 27, 2024 •

edited

Loading