Skip to content

Norm API for Lattice #877

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 28 commits into from
May 26, 2025
Merged

Norm API for Lattice #877

merged 28 commits into from
May 26, 2025

Conversation

emirsoyturk
Copy link
Contributor

Describe the changes

This PR adds Norm API for Lattices

Describe the rational

Why is this change necessary?

Does it increase performance?

Backend branches

Replace "main" with the branch this PR should work with

cuda-backend-branch: emir/norm

metal-backend-branch: main

@emirsoyturk
Copy link
Contributor Author

this is new version of #834

two open comments from old PR

one more interesting case is large values since norm looks at the values between (-q/2,q/2] so values close to q should be low norm too. For example norm(q-1)=norm(1)=1.
You can maybe use balanced decomposition on a random vector and check it is low norm as it should be.

Originally posted by @yshekel in #834 (comment)

maybe input_a and input_b may have different size. @Tomer-Solberg is it interesting?
Currently we assume at most 2^16 elements, each at most sqrt(q) in value so we only need 80b but we can support different sizes if required.

Originally posted by @yshekel in #834 (comment)

jeremyfelder
jeremyfelder reviewed Apr 29, 2025
View reviewed changes
Copy link
Collaborator

@jeremyfelder jeremyfelder left a comment

Choose a reason for hiding this comment

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

Overall looks good, I left a few comments

icicle/backend/cpu/src/ring/cpu_norm.cpp
Comment on lines +63 to +66
if (q < 0) {
ICICLE_LOG_ERROR << "Field modulus q must be less than 64 bits; received q = " << q;
return eIcicleError::INVALID_ARGUMENT;
}
Copy link
Collaborator

Choose a reason for hiding this comment

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

This should probably be a compile time check so we don't build libs that will fail here.

Copy link
Collaborator

Choose a reason for hiding this comment

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

you are right. I originally wrote it like this in other APIs because I couldn't make it a compile time check but maybe it's possible to do.

Copy link
Collaborator

Choose a reason for hiding this comment

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

Is the static_assert at the top of this file basically doing this check?

jeremyfelder
jeremyfelder reviewed May 13, 2025
View reviewed changes
@emirsoyturk emirsoyturk requested a review from yshekel May 14, 2025 07:05
@emirsoyturk emirsoyturk requested a review from jeremyfelder May 14, 2025 07:05
@emirsoyturk emirsoyturk merged commit 3fbdaba into main May 26, 2025
26 of 35 checks passed
@emirsoyturk emirsoyturk deleted the emir/norm branch May 26, 2025 08:11
@github-actions github-actions bot locked and limited conversation to collaborators May 26, 2025
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Reviewers

@yshekel yshekel yshekel approved these changes

@jeremyfelder jeremyfelder jeremyfelder approved these changes

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@emirsoyturk @yshekel @jeremyfelder