How to compute the maximum value of a vector and its index

[macknight]

Hi,
Assume I have a 1024-element vector, is there any way for me to find out the maximum number of this vector? And further more, the index of this maximum number?

BR

[Pro7ech]

To compute max(a,b):

If you are using BFV/BGV: https://petsymposium.org/popets/2021/popets-2021-0046.pdf

If you are using CKKS: https://www.computer.org/csdl/journal/tq/5555/01/09517029/1wau0zex2z6 (eprint is down at the time of this post)
Else you can compose CKKS with lookup tables to evaluate non-linear functions, such as sign or ReLU. See the example in lattigo/examples/ckks/advanced/lut -> max(a, b) = b + ReLU(a-b) and ReLU(x) = x * sign(x) where sign(x) = 0 if x < 0 else 1.

To compute index_max(vector):

Compose the above with an FFT-like algorithm, comparing pairs of elements. After log2(vector_size) iterations, you'll end up with a vector encrypting all zero except 1 a the index of the of the maximum value. You can get the value of this index by doing an inner product with a plaintext vector encoding the position of each index.

[macknight]

To compute max(a,b):

If you are using BFV/BGV: https://petsymposium.org/popets/2021/popets-2021-0046.pdf

If you are using CKKS: https://www.computer.org/csdl/journal/tq/5555/01/09517029/1wau0zex2z6 (eprint is down at the time of this post) Else you can compose CKKS with lookup tables to evaluate non-linear functions, such as sign or ReLU. See the example in lattigo/examples/ckks/advanced/lut -> max(a, b) = b + ReLU(a-b) and ReLU(x) = x * sign(x) where sign(x) = 0 if x < 0 else 1.

To compute index_max(vector):

Compose the above with an FFT-like algorithm, comparing pairs of elements. After log2(vector_size) iterations, you'll end up with a vector encrypting all zero except 1 a the index of the of the maximum value. You can get the value of this index by doing an inner product with a plaintext vector encoding the position of each index.

Your reply looks impressive!
And is FFT-like algorithm meaning a fast Fourier transform (FFT) is an algorithm?

BR

[Pro7ech]

Yes, FFT refers to fast Fourier transform. FFT-like means that the approch is similar in the way it is operating between pairs of elements recursively