Execution of rational ellipsoid coefficient computation
ProvedLax109476Proofs.RamEllipsoidCoefficients.computeCoefficients_specalgorithmscomputational-complexitylinear-programming
Let be the dimension and the rational quadratic-form value. Let be the precision grids, a height and magnitude bound, a height bound for the resulting five coefficients, and the machine modulus. Assume the explicit intermediate word-range inequalities and that the scalar input fields and five allocated zero coefficient entries are present. The coefficient command writes exactly the implementation's vector and preserves its scalar input:
Here is the binary length of . The vector contains the rational scaling, rank-one, center, inflation and diagonal coefficients for the rounded ellipsoid update. This is a reusable operational specification of their computation, including the necessary arithmetic bounds.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeOperationalInterfaces
Formal statement
theorem Lax109476Proofs.RamEllipsoidCoefficients.computeCoefficients_spec : ∀ (B n M C D E : ℕ) (q : ℚ),
2 ≤ n →
0 < q →
Lax109476Proofs.RationalArithmeticBounds.Height q M →
n ≤ M →
D ≤ M →
E ≤ M →
0 < D →
0 < E →
n ^ 2 < B →
(E + 1) ^ 2 < B →
2 * M ^ 2 + 3 < B →
(2 * (M ^ 3 + 2) + 1) ^ 2 + M ^ 3 + 3 < B →
C < B →
(∀ v ∈ Lax109476Proofs.RamEllipsoidCoefficients.coefficients n q D E,
Lax109476Proofs.RationalArithmeticBounds.Height v C) →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamEllipsoidCoefficients.ScalarInput n q D E σ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.coeff" (List.replicate 5 0) σ)
Lax109476Proofs.RamEllipsoidCoefficients.computeCoefficients
(fun (x τ : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamRationalArrays.Represents "ell.coeff"
(Lax109476Proofs.RamEllipsoidCoefficients.coefficients n q D E) τ ∧
Lax109476Proofs.RamEllipsoidCoefficients.ScalarInput n q D E τ)
(582 * M.size + 687) := by sorrySource