About parallel evaluation of chebyshev polynomials

Library Questions
1

Hello all,

Following the issue I raised in this thread, I created a fork of the library where I defined the function EvalChebyshevSeriesPSBatch(c, {coeffs1, coeffs2, ...}, a, b) that somewhat extends EvalChebyshevSeriesPS(c, coeffs, a, b).

The fork is available here and contains an example called batched_chebyshev_example.cpp, whose output is the following:

N: 4096

// SINGLE poly
Test with 6 coefficients [ 1 2 3 4 5 6 ] over x = 0.1, 0.2
(4.06096, 4.40272, ... ); Estimated precision: 29 bits

// SINGLE poly
Test with 6 coefficients [ 4 1.5 2 0.5 0.1 2 ] over x = 0.1, 0.2
(1.0944, 1.93552, ... ); Estimated precision: 28 bits

// MULTI poly
Now parallelizing the two polynomials in two slots, the first refers to x = 0.1 and coeffs1, the second to x = 0.2 and coeffs2
(4.06096, 1.93552, ... ); Estimated precision: 28 bits


******

// SINGLE poly
Test with 50 coefficients [ 3.4 1.2 0.8 1.3 0 2.3 1.1 0.6 0.3 0.6 3 2.1 0.3 2.7 2.9 1.7 2.2 0.5 0.5 0.6 1.6 0.8 0.6 0.8 1.8 1.4 1.6 1.7 2.5 2.2 0.2 1.6 1.9 1.2 1.9 0.1 1 0.1 1.4 2.5 2.9 2.9 2.7 0.2 0 0.2 2 0.8 1.3 2 ] over x = 0.1, 0.2
(-5.7511505, 5.2419634, ... ); Estimated precision: 25 bits

// SINGLE poly
Test with 50 coefficients [ -0.5 1.8 1.3 1.9 -1.1 1.7 -2 1.9 -1.8 -1.8 1.8 -0.4 -0.5 -1.1 1.5 -1 -0.3 0.4 -1.2 -0.4 -0.2 -0.2 -1.8 1.6 -1.4 -1.4 0.1 -1.3 -1.7 -0.7 -0.6 0.7 1.8 -0.5 -0.3 -1.8 -2 -0.7 1 0.2 1.5 0 -1.1 1.2 -0.4 2 0.5 -2 -1.6 0.7 ] over x = 0.1, 0.2
(-10.209841, -0.032831066, ... ); Estimated precision: 11 bits

// MULTIPLE poly
Now parallelizing the two polynomials in two slots, the first refers to x = 0.1 and coeffs1, the second to x = 0.2 and coeffs2
(-5.7510871, -0.032547875, ... ); Estimated precision: 12 bits


Process finished with exit code 0

Of course it works with CKKS only. The idea is simple, given a ciphertext containing

[a, b, \dots]

the function allows to compute

[p_1(a), p_2(b), \dots]

where p_i is a polynomial in Chebyshev basis, defined by its set of coefficients. The function currently accepts a number of polynomials p_i that is equal to the number of slots.
Notice that, currently, the standard EvalChebyshevSeriesPS only allows to evaluate

[p(a), p(b)]

for a given polynomial p.

The definitions in the headers are already documented, although I am planning to add more documentations and (moreover) tests in the following days.
In particular, the new functions are

  • In cryptocontext.h
    – EvalLinearWSumBatch
    – EvalLinearWSumMutableBatch
    – EvalChebyshevSeriesPSBatch

  • In ckksrns-advancedshe.h
    – EvalChebyshevSeriesPSBatch
    – EvalLinearWSumBatch
    – EvalLinearWSumMutableBatch

Additionally, I will also better embed the function by returning OPENFHE_THROW if something goes wrong.

Possible cases

The use cases are many, the first that comes to my mind is that it simplifies a possible implementation of [BK25], where different modulus reduction are performed in the different slots.

Feedbacks

Let me know if you can catch some bugs, I only run a few tests but would be nice to stress it. Hopefully at some point could be a standard functionality in the library.:slight_smile: Also I am not an expert of C++, so maybe you can find some weird or wrong lines of code.
Extra: It would be nice to have the same functions also for standard power basis polynomials as well.

1 Like