Alexander Viand

While looking at `bgv.mul`, I noticed it (incorrectly) wouldn't allow having sequential multiplications without relineraization in-between. With the fix in (currently PR #733), I'd suggest the simplest way to realize...

> I didn't realize that relinearizing after repeated multiplications is a thing people do. It's not really something people do outside of _very_ specific use cases. I think quite a...

> do we have a possibility to reach at something like this `mul3(_, relin(mul2(_, relin(mul1))))` I think so: if we had `mul3(_, mul2(_, mul1(_,_)))` to begin with, the RHS pattern...

> So at this stage could we optimize the above to `mul3(_ ,relin(mul2( lmul1(x,y), rmul1(y,x))))` such that we relin only after `mul2` ? I don't think that'd be valid (assuming...

> Looking back on https://www.jeremykun.com/2023/11/15/mlir-a-global-optimization-and-dataflow-analysis/#an-ilp-optimization-pass, I'm not seeing any real obstacle to adapting that ILP to this problem. Mh, wouldn't you need to keep all the noise-related stuff in the...

Btw, I realized that my "simple DDR Pattern"-based approach probably wouldn't work, as it wouldn't correctly handle something like: ```llvm // Assume arg0, arg1, arg2, arg3 are "appropriately typed" function...

Let me also add two FHE-specific references that are likely to be useful (in addition to more general work on fast NTT/modular arithmetic implementation): * [Intel HEXL: Accelerating Homomorphic Encryption...

> This ticket should be split into more manageable pieces. I think they might be [...] > If you agree I can go ahead and file those issues, and this...

> Since this was written, the following are completed (though may not be fully polished) > > * [x] Support lowering a linalg.generic of polymuls (should already be supported by...

@edwjchen Thanks for your summary and discussion on this in the last meeting (sorry for not being there 😴) The basic approach of "pick a batching approach, then generate the...