OptimizeRelinearizationPasses

-optimize-relinearization

Optimize placement of relinearization ops

This pass defers relinearization ops as late as possible in the IR. This is more efficient in cases where multiplication operations are followed by additions, such as in a dot product. Because relinearization also adds error, deferring it can reduce the need for bootstrapping.

In this pass, we use an integer linear program to determine the optimal relinearization strategy. It solves an ILP for each func op in the IR.

The assumptions of this pass include:

• All return values of functions must be linearized.
• All ciphertext arguments to an op must have the same key basis
• Rotation op inputs must have be linearized.

For an ILP model specification, see the docs at the HEIR website. The model is an adaptation of the ILP described in a blog post by Jeremy Kun.