Add chebyshev Iteration #1289

yhmtsai · 2023-02-22T16:12:44Z

It adds the Chebshev iteration in https://en.wikipedia.org/wiki/Chebyshev_iteration
The second-order richardson uses a similar formula but the scalars are constant in all iteration. Chebyshev Iteration update the scalar from the previous one (the scalar are the same if upper/lower eigval does not change)

MarcelKoch · 2023-03-14T13:55:36Z

Do you intend adding an eigenvalue estimation? I think that would be very helpful, because most times users don't have that available. I think PETSc is also doing that.
I briefly searched for that and here are some references that might be interesting for that:

I think this is the GMRES version used by PETSC to compute the estimate: https://petsc.org/release/docs/manualpages/KSP/KSPAGMRES/

yhmtsai · 2023-03-20T11:30:07Z

@MarcelKoch thanks for providing these reference.

I do not think I will put them in this pull request.

From https://doi.org/10.1137/0907057, they introduce the algorithm
adaptive chebyshev iteration
Perform m-step GMRES and use the information from the Hessenberg matrix to get the estimation of eigenvalue (I may be wrong),
and then perform https://link.springer.com/article/10.1007/BF01389971 to get the parameter for chebchev
Repeat these two steps until converge
This will be more like a standalone solver not a smoother for multigrid because it will require several steps on GMRES, which is too expensive IMO.
We can introduce by with_adaptive(GMRES LinOpFactory)

From https://petsc.org/release/docs/manualpages/KSP/KSPCHEBYSHEV/#kspchebyshev,
More precisely, https://petsc.org/release/docs/manualpages/KSP/KSPChebyshevEstEigSet/
They use Lanczo or GMRES to get the maximum estimation to decide the parameter by following
min-eig-boundary = a * min-eigest + b * max-eigest = 0.1 max-eigest (default), and
max-eig-boundary = c * min-eigest + d * max-eigest = 1.1 max-eigest (default)
(because min_eigest is usually inaccurate)
By this, user can use the information by GMRES and generate min/max eig boundary for Chebyshev, so we do not need additional parameter?
It only does once in generation, so this is more usable for Multigrid

For GMRES, we need to get the Hessenberg out and compute eigenvalue on it.
GMRES eigenvalue and Lanczo are related to #135

sonarqubecloud · 2023-03-21T23:48:49Z

Kudos, SonarCloud Quality Gate passed!

0 Bugs
0 Vulnerabilities
0 Security Hotspots
8 Code Smells

44.3% Coverage
7.1% Duplication

MarcelKoch

Besides the comments left below, I want to mention the num_keep and num_generated mechanic. That needs some explaination, because right now I don't understand what that is for. It seems like some sort of restart mechanic, but I might be wrong there. Also, exposing this to the user seems confusing to me.

MarcelKoch · 2023-04-06T07:06:22Z

include/ginkgo/core/solver/chebyshev.hpp

+        /**
+         * The number of scalar to keep
+         */
+        int GKO_FACTORY_PARAMETER_SCALAR(num_keep, 2);


It is not clear what this parameter is for.

Perhaps this means, construct Chebyshev polynomials until degree num_keep, and after that just do IR with these polynomial?

no, num_keep is to keep the generated scalar in the storage.
alpha and beta are changed by iteration, but they are fixed by the given bound.
It's used for fixed iteration runs because we do not need to refill these scalars for different apply

But shouldn't we then just keep all scalars?

when using it as normal solver, we may not have the maximum iteration information.
allocating one big dense matrix and then moving them to another one when full may not be a good approach.
we can also add the ability of workspace such that it can handle the std::vector then it should be more flexible for uncertain size.

I can not assume that there's an iteration criterion. It can contain the residual norm or time criterion.
If we assume that, we should provide the standalone iteration parameter.
Users do not need to know the implementation details.
The statement is to keep how many scalars for chebyshev to avoid the refill overhead.
I can introduce this usage later when we have the use case.
I think it should help the situation when kernel launch overhead is noticeable.

You are right, this is very useful to negate the overhead. Still, I think we can assume that there is an iteration criterion somewhere in the combined one and use that. If not, we would just throw.

You could set the default value to unspecified, which you define before. When the solver is generated, you can check if the parameter is unspecified and then try to extract an iteration criterion from the criteria. If that doesn't work, you throw with a message to either pass an iteration criterion or set this parameter to something else.
Or alternatively, just replace the criteria parameter with a iterations parameter and move the class into the preconditioner namespace. I think that is also a fine option, since that would be the main use case anyway.

I have moved it to based on the given iteration from stopping criterion.
It is only increased after creating object.
I also think whether staying a fixed number is enough or not.

Thanks, I think it should be fine the way it is now.

MarcelKoch · 2023-04-06T07:09:33Z

include/ginkgo/core/solver/chebyshev.hpp

+/**
+ * Chebyshev iteration is an iterative method that uses another coarse
+ * method to approximate the error of the current solution via the current
+ * residual. It has another term for the difference of solution. Moreover, this


Suggested change

* residual. It has another term for the difference of solution. Moreover, this

* residual. The solution is then updated using the Chebyshev polynomials. Moreover, this

Is that what the sentence is trying to say? Anyway, I think it should be mentioned somewhere that this uses these polynomials.

the solution x_i is also based on the $x_{i-1} - x_{i-2}$

TBH I don't see the relevance of that. Has that any effect for the user?

no, I only try to explain the algorithm's difference from IR. IR uses $x += \alpha M^{-1}r$, but chebyshev uses $x += \alpha_i M^{-1} r + \beta_i (x_{i-1} - x_{i-2})$ $(x_{i-1} - x_{i-2})$ is the additional term against IR

I still think this has to be rephrased

I try to rephrase it again. Could you take a look?

include/ginkgo/core/solver/chebyshev.hpp

core/solver/chebyshev.cpp

include/ginkgo/core/solver/chebyshev.hpp

reference/test/solver/chebyshev_kernels.cpp

core/test/solver/chebyshev.cpp

vasilisge0

I am fine with merging this PR when corrections in parts of the documentation that are pointed out (comments) take place. I could understand what num_keep variable was used for but perhaps a more descriptive name would be better.

sonarqubecloud · 2023-08-08T22:32:36Z

Kudos, SonarCloud Quality Gate passed!

0 Bugs
0 Vulnerabilities
0 Security Hotspots
21 Code Smells

42.6% Coverage
4.4% Duplication

The version of Java (11.0.3) you have used to run this analysis is deprecated and we will stop accepting it soon. Please update to at least Java 17.
Read more here

MarcelKoch

LGTM, but I would like to resolve some of my earlier issues. Other than that only minor nits.

core/solver/chebyshev.cpp

MarcelKoch · 2023-10-13T10:38:19Z

include/ginkgo/core/solver/chebyshev.hpp

+/**
+ * Chebyshev iteration is an iterative method that uses another coarse
+ * method to approximate the error of the current solution via the current
+ * residual. It has another term for the difference of solution. Moreover, this


I still think this has to be rephrased

include/ginkgo/core/solver/chebyshev.hpp

core/test/solver/chebyshev.cpp

reference/test/solver/chebyshev_kernels.cpp

sonarqubecloud · 2023-10-19T19:36:47Z

Kudos, SonarCloud Quality Gate passed!

0 Bugs
0 Vulnerabilities
1 Security Hotspot
27 Code Smells

59.4% Coverage
5.2% Duplication

The version of Java (11.0.3) you have used to run this analysis is deprecated and we will stop accepting it soon. Please update to at least Java 17.
Read more here

include/ginkgo/core/solver/chebyshev.hpp

core/test/solver/chebyshev.cpp

Co-authored-by: Marcel Koch <marcel.koch@kit.edu>

Co-authored-by: Tobias Ribizel <ribizel@kit.edu>

Co-authored-by: Tobias Ribizel <mail@ribizel.de>

Co-authored-by: Marcel Koch <marcel.koch@kit.edu>

update

sonarqubecloud · 2025-04-17T04:05:55Z

Quality Gate passed

Issues
41 New issues
0 Accepted issues

Measures
1 Security Hotspot
87.4% Coverage on New Code
5.3% Duplication on New Code

See analysis details on SonarQube Cloud

codecov · 2025-04-17T04:11:51Z

Codecov Report

Attention: Patch coverage is 91.74147% with 46 lines in your changes missing coverage. Please review.

Project coverage is 88.73%. Comparing base (e797f4a) to head (7904562).
Report is 20 commits behind head on develop.

Files with missing lines	Patch %	Lines
core/solver/chebyshev.cpp	78.10%	30 Missing ⚠️
reference/test/solver/chebyshev_kernels.cpp	96.77%	5 Missing ⚠️
common/unified/solver/chebyshev_kernels.cpp	69.23%	4 Missing ⚠️
test/solver/solver.cpp	0.00%	4 Missing ⚠️
core/device_hooks/common_kernels.inc.cpp	0.00%	2 Missing ⚠️
core/config/solver_config.cpp	0.00%	1 Missing ⚠️

Additional details and impacted files

@@             Coverage Diff             @@
##           develop    #1289      +/-   ##
===========================================
- Coverage    89.36%   88.73%   -0.64%     
===========================================
  Files          824      831       +7     
  Lines        68983    69571     +588     
===========================================
+ Hits         61649    61732      +83     
- Misses        7334     7839     +505

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

yhmtsai added the 1:ST:WIP This PR is a work in progress. Not ready for review. label Feb 22, 2023

yhmtsai self-assigned this Feb 22, 2023

ginkgo-bot added reg:build This is related to the build system. reg:testing This is related to testing. mod:core This is related to the core module. mod:reference This is related to the reference module. type:solver This is related to the solvers labels Feb 22, 2023

yhmtsai force-pushed the cheb_iter branch from fa439a5 to 7d38ecb Compare March 21, 2023 12:34

yhmtsai 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 Mar 21, 2023

MarcelKoch requested changes Apr 6, 2023

View reviewed changes

upsj requested a review from vasilisge0 April 6, 2023 15:51

vasilisge0 reviewed Apr 14, 2023

View reviewed changes

yhmtsai force-pushed the cheb_iter branch 3 times, most recently from c88ea63 to f9d0e28 Compare August 8, 2023 10:06

yhmtsai force-pushed the cheb_iter branch from 58530f8 to a7dcc2a Compare August 9, 2023 07:22

yhmtsai force-pushed the cheb_iter branch from a7dcc2a to edee59a Compare September 12, 2023 09:43

upsj self-requested a review September 18, 2023 12:27

yhmtsai force-pushed the cheb_iter branch from edee59a to 409a2e6 Compare October 4, 2023 15:01

yhmtsai requested review from MarcelKoch and vasilisge0 October 13, 2023 10:07

MarcelKoch requested changes Oct 13, 2023

View reviewed changes

yhmtsai force-pushed the cheb_iter branch from 409a2e6 to aeab966 Compare October 19, 2023 09:37

MarcelKoch reviewed Oct 20, 2023

View reviewed changes

include/ginkgo/core/solver/chebyshev.hpp Outdated Show resolved Hide resolved

include/ginkgo/core/solver/chebyshev.hpp Outdated Show resolved Hide resolved

core/test/solver/chebyshev.cpp Show resolved Hide resolved

yhmtsai force-pushed the cheb_iter branch from 2d38047 to c0ef0d9 Compare March 25, 2025 12:57

yhmtsai requested a review from MarcelKoch March 25, 2025 12:58

MarcelKoch approved these changes Mar 25, 2025

View reviewed changes

yhmtsai added 1:ST:ready-to-merge This PR is ready to merge. and removed 1:ST:ready-for-review This PR is ready for review labels Apr 15, 2025

yhmtsai and others added 18 commits April 15, 2025 13:25

init chebyshev

1b3671b

add the check for kept data and remove lend

53bd8ac

core test

9cbb9ba

change to foci

9bc798c

use iteration from stop criterion and update doc

cdabda4

extract the split residual update and update test

8bf1344

Co-authored-by: Marcel Koch <marcel.koch@kit.edu>

use preconditioner not inner_solver for chebyshev

c99b9bf

Co-authored-by: Marcel Koch <marcel.koch@kit.edu>

add chebyshev test and fix the number of generated

10c939f

use scalar from ws and move some local variables

a63380a

Co-authored-by: Marcel Koch <marcel.koch@kit.edu>

review update

882fc5e

Co-authored-by: Marcel Koch <marcel.koch@kit.edu>

update with new format

677cf24

add config for chebyshev

9a8663e

use mixed_type in test properly and update documentation

4d44a74

Co-authored-by: Tobias Ribizel <ribizel@kit.edu>

add fused kernel for chebyshev

9d12c65

pass alpha/beta by value to kernel and add test

83df775

use double/complex<double> for fosi

c372878

Co-authored-by: Tobias Ribizel <mail@ribizel.de>

rename type and variable, update documentation and format

e8cba61

update the type name and add more assert to check foci

0351f48

Co-authored-by: Marcel Koch <marcel.koch@kit.edu>

yhmtsai force-pushed the cheb_iter branch from c0ef0d9 to 0351f48 Compare April 15, 2025 11:25

fix the circular dep

7904562

yhmtsai merged commit 8da182a into develop Apr 17, 2025
14 checks passed

yhmtsai deleted the cheb_iter branch April 17, 2025 09:07

	* residual. It has another term for the difference of solution. Moreover, this
	* residual. The solution is then updated using the Chebyshev polynomials. Moreover, this

Add chebyshev Iteration #1289

Add chebyshev Iteration #1289

Uh oh!

Conversation

yhmtsai commented Feb 22, 2023

Uh oh!

MarcelKoch commented Mar 14, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

yhmtsai commented Mar 20, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sonarqubecloud bot commented Mar 21, 2023

Uh oh!

MarcelKoch left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

yhmtsai Aug 7, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

vasilisge0 left a comment

Choose a reason for hiding this comment

Uh oh!

sonarqubecloud bot commented Aug 8, 2023

Uh oh!

MarcelKoch left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

sonarqubecloud bot commented Oct 19, 2023

Uh oh!

MarcelKoch commented Mar 14, 2023 •

edited

Loading

yhmtsai commented Mar 20, 2023 •

edited

Loading

yhmtsai Aug 7, 2023 •

edited

Loading

codecov bot commented Apr 17, 2025 •

edited

Loading