Complexification is a recent optimization described in several papers: Thor, Powerformer, and Tricycle. Each paper describes their own method and there are many ways to use complexification optimizations, but the general concept boils down to this: Pack data twice as efficiently during matrix multiplications (and other linear operations) by using CKKS's native support for complex numbers. This has the performance effect of potentially halving the number of operations required.
Generally speaking, complexification is most applicable when matrix dimensions span more than one ciphertext (often called block matrix multiplications). Either the encrypted matrices or the plaintext matrices may be complexified. (It's possible to have two matrix operands be complexified as well.)
Typically, there's a step to "extract" out only the real component or imaginary component. This is usually accomplished as follows: Suppose we have a value x = a + bi. Then if we only want the real component, we simply do Real(x) = (x + conj(x)) / 2 = ((a + bi) + (a - bi)) / 2 = a. Conjugation is an available operation in CKKS, is a key switching operation, and does require a conjugation key. To save one level of multiplicative depth, the division by two can also folded into the plaintext weights. If we only want the imaginary component (which we'll extract into a real value), then we can simply compute Im(x) = i (conj(x) - x) / 2 = i ((a - bi) - (a + bi)) / 2 = b. Some homomorphic encryption libraries are able to support the multiplication by i without consuming a multiplication level while some libraries are required to consume a level.
What all this means, is that you can do matrix multiplications (or other linear operations) using both the real and imaginary components, and then extract out only the real and/or imaginary components that you need, and then continue the rest of the operation from there.
Complexification is a recent optimization described in several papers: Thor, Powerformer, and Tricycle. Each paper describes their own method and there are many ways to use complexification optimizations, but the general concept boils down to this: Pack data twice as efficiently during matrix multiplications (and other linear operations) by using CKKS's native support for complex numbers. This has the performance effect of potentially halving the number of operations required.
Generally speaking, complexification is most applicable when matrix dimensions span more than one ciphertext (often called block matrix multiplications). Either the encrypted matrices or the plaintext matrices may be complexified. (It's possible to have two matrix operands be complexified as well.)
Typically, there's a step to "extract" out only the real component or imaginary component. This is usually accomplished as follows: Suppose we have a value
x = a + bi. Then if we only want the real component, we simply doReal(x) = (x + conj(x)) / 2 = ((a + bi) + (a - bi)) / 2 = a. Conjugation is an available operation in CKKS, is a key switching operation, and does require a conjugation key. To save one level of multiplicative depth, the division by two can also folded into the plaintext weights. If we only want the imaginary component (which we'll extract into a real value), then we can simply computeIm(x) = i (conj(x) - x) / 2 = i ((a - bi) - (a + bi)) / 2 = b. Some homomorphic encryption libraries are able to support the multiplication by i without consuming a multiplication level while some libraries are required to consume a level.What all this means, is that you can do matrix multiplications (or other linear operations) using both the real and imaginary components, and then extract out only the real and/or imaginary components that you need, and then continue the rest of the operation from there.