Execution of the rounded ellipsoid center update
ProvedLax109476Proofs.RamCenterUpdate.updateCenter_ellipsoid_specalgorithmscomputational-complexitylinear-programming
Let be a rational matrix, let , and let be the rounding grid. Let be the coefficient vector, with its center coefficient equal to . Let bound the heights of , and this coefficient, and assume , and the prescribed center-overflow bound for modulus . Given encoded and three next-center arrays of length , the center command produces
It preserves and runs in at most steps. The coefficient vector has at least three entries. The result connects a coordinate loop to the mathematical rounded-center update.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeOperationalInterfaces
Formal statement
theorem Lax109476Proofs.RamCenterUpdate.updateCenter_ellipsoid_spec : ∀ (B n M D : ℕ) (A : Matrix (Fin n) (Fin n) ℚ) (a c : Fin n → ℚ) (gs : List ℚ) (hg : 2 < gs.length),
1 ≤ M →
(∀ (j : Fin n), Lax109476Proofs.RationalArithmeticBounds.Height (A.mulVec a j) M) →
(∀ (j : Fin n), Lax109476Proofs.RationalArithmeticBounds.Height (c j) M) →
Lax109476Proofs.RationalArithmeticBounds.Height gs[2] M →
gs[2] = 1 / ((↑n + 1) * Lax109476Proofs.RationalRounding.sqrtUpper (a ⬝ᵥ A.mulVec a) D) →
D ≤ M →
0 < D →
n < B →
2 * Lax109476Proofs.RamCenterCoordinate.centerCap M ^ 2 + 3 < B →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamRationalArrays.Represents "ell.u" (List.ofFn (A.mulVec a)) σ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.center" (List.ofFn c) σ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.coeff" gs σ ∧
(σ.arrs "ell.nextcenter.s").length = n ∧
(σ.arrs "ell.nextcenter.n").length = n ∧
(σ.arrs "ell.nextcenter.d").length = n ∧ σ.vars "vec.n" = n ∧ σ.vars "grid.D" = D)
Lax109476Proofs.RamCenterUpdate.updateCenter
(fun (x τ : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamRationalArrays.Represents "ell.nextcenter"
(List.ofFn (Lax109476Proofs.EllipsoidCenter.roundedCenter n A a c D)) τ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.u" (List.ofFn (A.mulVec a)) τ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.center" (List.ofFn c) τ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.coeff" gs τ ∧
τ.vars "vec.n" = n ∧ τ.vars "grid.D" = D)
(33 * n + 18 +
((180 * (Lax109476Proofs.RamCenterCoordinate.centerCap M).size + 318 + 4 + 4) * n + 6)) := by sorrySource