Use smaller extended domains where possible during proving

[str4d]

We perform polynomial operations over an extended Lagrange basis that is large enough to contain the results of evaluating expressions on the largest polynomials:

halo2/src/poly/domain.rs

Lines 46 to 52 in 18e13b1

	// We need to work within an extended domain, not params.k but params.k + i
	// for some integer i such that 2^(params.k + i) is sufficiently large to
	// describe the quotient polynomial.
	let mut extended_k = k;
	while (1 << extended_k) < (n * quotient_poly_degree) {
	extended_k += 1;
	}

However, not all of the polynomials need the full extended domain. We could instead group the polynomials on the basis size they require, and then evaluate sub-expressions that only involve these polynomials using their respective basis. It is possible to efficiently extract a smaller basis from a larger one, so the cost of generating these multiple bases should be small compared to the efficiency gains from reducing the basis sizes used in many of the circuit operations.

This blocks on #360 because we need to "transpose" how we operate on polynomials (moving parallelization to the start of the call chain instead of the end) for that issue, and once we are applying full expressions to chunks of polynomials, it becomes natural to introduce smaller polynomial bases.

[str4d]

I currently believe that addressing this issue would resolve the performance problem noted in #418 (comment).

[str4d]

Actually, having looked more closely at #418 (comment), I think it's being caused by the fact that we don't cache rotated polynomials, so if the same (polynomial, rotation) pair is used multiple times within an expression, we'll rotate it multiple times. So I think this will actually be addressed by #360, where we'll need to pre-compute all the polynomials used in an expression in order to the parallelize at the top, and in doing so will eliminate duplicate rotations.

[miha-stopar]

Sorry for a dumb question, but I don't see which polynomials need an extended domain? I was actually wondering how and whether at all extended domain is needed for custom constraint polynomials because I am having some issues with a high degree for Merkle Patricia Trie circuit which consequently uses quite an extension of the original domain.

[miha-stopar]

Sorry for a dumb question, but I don't see which polynomials need an extended domain? I was actually wondering how and whether at all extended domain is needed for custom constraint polynomials because I am having some issues with a high degree for Merkle Patricia Trie circuit which consequently uses quite an extension of the original domain.

Ah, had another look and I think I see it now. There is a poly (like in vanishing/prover.rs, construct method):

h_poly = l^0 + expr_0 + l^1 * expr_1 + ... + l^n * expr_n

where each expr_i is of the form p(a(x), b(x), c(x)) where p is a poly of the degree at most m and a(x), b(x), c(x) describe the columns (let's say we only have three). Polynomials a(x), b(x), c(x) are of the degree at most n, so h_poly is a poly of degree (at most) m*n - and after dividing by vanishing polynomial, we need enough space to interpolate it (which we don't have if the domain is not extended).

[str4d]

Yep (though I think it's actually (m-1)*n IIRC - there's an off-by-one in there of which I always forget the origin). The idea for this issue is to break down and combine the various expr_i into sub-expressions involving columns that are only used at common smaller degrees. e.g. if the maximum degree is 7, but a(x) and b(x) are only involved in degree-4 sub-expressions, then we only need to operate on c(x) in the largest extension domain.

[miha-stopar]

Off-by-one is probably because of division by vanishing poly x^n - 1 which reduces the degree by n. I was thinking a bit how to implement this optimisation, but I worry it wouldn't be much of a speed up. The beauty of multi-opening is that there is FFT only for one polynomial needed, if there would be k-sub-expressions, FFT interpolation would be needed for each of them to get the final h poly. Do you think it's worth it?