Stored ellipsoid matrix-vector multiplication
OpenLax109476Proofs.RamMatrixVector.ellipsoidMulVec_specalgorithmscomputational-complexitygraph-theory
Let be a rational matrix and a rational vector, with every entry of height at most . Assume the stated dimension and arithmetic-cap word guards, initialized matrix and input buffers, and a zero output buffer. The bounded command computes the exact vector, preserves , and has the explicit quadratic-loop instruction bound:
This is a reusable source interface for composing the complete finite-program implementation.
Retired because the namespace-wrapped declaration compiled during publication but the proof-comparison parser rejects that header (expected token / unknown full theorem identifier). The mathematically identical, fully qualified declaration is Lax109476Proofs.RamMatrixVector.ellipsoidMulVec_spec_native.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces
Formal statement
namespace Lax109476Proofs.RamMatrixVector
theorem ellipsoidMulVec_spec : ∀ (B n H : Nat) (A : Matrix (Fin n) (Fin n) Rat) (c : Fin n → Rat),
Nat.le ((1:Nat)) H →
(∀ (k j : Fin n), Lax109476Proofs.RationalArithmeticBounds.Height (A k j) H) →
(∀ (j : Fin n), Lax109476Proofs.RationalArithmeticBounds.Height (c j) H) →
Nat.lt
(Nat.add
(Nat.add (Nat.add n n)
(Nat.mul n n))
((1:Nat)))
B →
Nat.lt
(Nat.add
(Nat.mul
((2:Nat))
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(Lax109476Proofs.RamDotProduct.cap n H) ((2:Nat))))
((3:Nat)))
B →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
And (@Lax109476Proofs.RamMatrixRows.MatrixRows n n "ell.shape" A σ)
(And (Lax109476Proofs.RamRationalArrays.Represents "ell.normal" (@List.ofFn Rat n c) σ)
(And
(Lax109476Proofs.RamRationalArrays.Represents "ell.u"
(@List.replicate Rat n (@OfNat.ofNat Rat (nat_lit 0) (@Rat.instOfNat (nat_lit 0)))) σ)
(@Eq Nat (σ.vars "vec.n") n))))
Lax109476Proofs.RamMatrixVector.ellipsoidMulVec
(fun (x τ : Lax808846Proofs.Imp.Env) =>
And
(Lax109476Proofs.RamRationalArrays.Represents "ell.u"
(@List.ofFn Rat n
(@Matrix.mulVec (Fin n) (Fin n) Rat
(@NonUnitalNonAssocRing.toNonUnitalNonAssocSemiring Rat
(@NonUnitalNonAssocCommRing.toNonUnitalNonAssocRing Rat
(@NonUnitalCommRing.toNonUnitalNonAssocCommRing Rat
(@CommRing.toNonUnitalCommRing Rat Rat.commRing))))
(Fin.fintype n) A c))
τ)
(And (@Lax109476Proofs.RamMatrixRows.MatrixRows n n "ell.shape" A τ)
(And (Lax109476Proofs.RamRationalArrays.Represents "ell.normal" (@List.ofFn Rat n c) τ)
(@Eq Nat (τ.vars "vec.n") n))))
(Nat.add
(Nat.mul
(Nat.add
(Nat.add
(Nat.add
(Nat.add
((4:Nat))
(Nat.add
(Nat.mul
(Nat.add
(Nat.add
(Nat.mul
((144:Nat))
(Lax109476Proofs.RamDotProduct.cap n H).size)
((216:Nat)))
((4:Nat)))
n)
((12:Nat))))
((21:Nat)))
((4:Nat)))
((4:Nat)))
n)
((8:Nat))) := by sorry
end Lax109476Proofs.RamMatrixVector
Source