Recovering the constant coefficient with bounded exact arithmetic
Only h_0=H(0) is needed. Let V_0 replace V's constant-coefficient column by b=Omega*y. Cramer's rule gives h_0=det(V_0)/(Omega*det(V)), with det(V) nonzero. Use fraction-free Gaussian elimination, not permutation enumeration or floating-point arithmetic, to compute the determinants. The standard method uses O(K^3) integer arithmetic operations, with row pivoting when necessary and exact divisions. Its retained entries are signed minors; intermediate products and differences still have polynomial bit length by the minor bound. The numerator matrix may be singular, yielding a zero answer. For clause-indicator factors, H(0) is an integer count, so the final division is exact.
0
1
Tags
Math