Execution of the rounded ellipsoid shape update
ProvedLax109476Proofs.RamShapeUpdate.updateShape_ellipsoid_specalgorithmscomputational-complexitylinear-programming
Let be a rational matrix, , a grid and an inflation parameter. Assume the coefficient vector has at least five entries and satisfies
Let bound the heights of , and these coefficients, with and the routine's explicit word-range bounds for modulus . Given their encodings and three next-shape arrays of length , the command writes in flattened order. It preserves and runs in at most steps. This links the matrix-entry loop to the mathematical rounded update.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeOperationalInterfaces
Formal statement
theorem Lax109476Proofs.RamShapeUpdate.updateShape_ellipsoid_spec : ∀ (B n M D : ℕ) (A : Matrix (Fin n) (Fin n) ℚ) (a : Fin n → ℚ) (gs : List ℚ) (hg : 4 < gs.length) (η : ℚ),
1 ≤ M →
n * n ≤ M →
(∀ (j : Fin n), Lax109476Proofs.RationalArithmeticBounds.Height (A.mulVec a j) M) →
(∀ (i j : Fin n), Lax109476Proofs.RationalArithmeticBounds.Height (A i j) M) →
Lax109476Proofs.RationalArithmeticBounds.Height gs[0] M →
Lax109476Proofs.RationalArithmeticBounds.Height gs[1] M →
Lax109476Proofs.RationalArithmeticBounds.Height gs[3] M →
Lax109476Proofs.RationalArithmeticBounds.Height gs[4] M →
D ≤ M →
0 < D →
n * n < B →
n < B →
2 * Lax109476Proofs.RamShapeCoordinate.shapeCap M ^ 2 + 3 < B →
gs[0] = ↑n ^ 2 / (↑n ^ 2 - 1) →
gs[1] = 2 / ((↑n + 1) * a ⬝ᵥ A.mulVec a) →
gs[3] = (1 + η) ^ 2 →
gs[4] = ↑n / ↑D →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamRationalArrays.Represents "ell.u" (List.ofFn (A.mulVec a))
σ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.shape"
(Lax109476Proofs.RamMatrixStorage.flatten A) σ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.coeff" gs σ ∧
(σ.arrs "ell.nextshape.s").length = n * n ∧
(σ.arrs "ell.nextshape.n").length = n * n ∧
(σ.arrs "ell.nextshape.d").length = n * n ∧
σ.vars "vec.n" = n ∧ σ.vars "grid.D" = D)
Lax109476Proofs.RamShapeUpdate.updateShape
(fun (x τ : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamRationalArrays.Represents "ell.nextshape"
(Lax109476Proofs.RamMatrixStorage.flatten
(Lax109476Proofs.EllipsoidCenter.roundedStepShape n A a D η))
τ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.u" (List.ofFn (A.mulVec a))
τ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.shape"
(Lax109476Proofs.RamMatrixStorage.flatten A) τ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.coeff" gs τ ∧
τ.vars "vec.n" = n ∧ τ.vars "grid.D" = D)
(33 * (n * n) + 26 +
((468 * (Lax109476Proofs.RamShapeCoordinate.shapeCap M).size + 690 + 4 + 4) *
(n * n) +
10)) := by sorrySource