Sparse exact principal solve preserves recursive frames and produces owned answer buffers
ProvedNearlyOptimalPPR.Computation.cached_principal_solve_memory_execLet be a nonempty injectively enumerated set of stored positive-degree vertices with and a represented right-hand side . Assume the enumeration is below the allocation frontier and disjoint from every owned frame, and that all index marks are bounded by the current epoch. Put
The principal-solve routine has a finite execution that preserves the represented logical recursive state and its heap mass, builds owned enumeration/answer buffers, and stores the principal solution extended by zero outside . With record width , its instruction count is at most , and its charged work is at most initial work plus and the exact-solve charge. Existing output is preserved. The epoch advances by one and all index marks remain bounded by it.
This theorem separates sparse numeric assembly and valid primitive invocation from later potential propagation and key refresh.
import Definitions.Def_NearlyOptimalPPR_Computation_compiler_runtime import Definitions.Def_NearlyOptimalPPR_Computation_compiler_buffers open Finset Matrix open scoped ENNReal set_option autoImplicit false noncomputable section attribute [local instance] Classical.propDecidable
namespace NearlyOptimalPPR.Computation
open SparseQueue
theorem cached_principal_solve_memory_exec (m : SolveModel) {n k : ℕ} (g : InputGraph n) (ω : ℕ → Bool)
(logical : RecursiveState n) (s : Fin n) (α ε : ℝ) (ell length offset : ℕ)
(base enumBase epoch : ℤ) (hEnumBase : 0 ≤ enumBase)
(e : Fin k → Fin n) (he : Function.Injective e) (hk : 0<k) (hd : ∀ i, 0<g.graph.degree (e i))
(hα : 0<α ∧ α<1) (b : Fin n → ℝ) (st : MachineState) (hh : st.scalar.halted=false)
(pm : RecursiveMachineMemory g s α ε ell length logical st) (hDepth : logical.top ≤ ell)
(hmem : ∀ j, e j ∈ logical.stored) (hEnum : EnumerationStored st.scalar.integerMemory enumBase e)
(hEnumBelow : ∀ i : Fin k, enumBase+(i.val : ℤ) < base)
(hForeign : ∀ i : Fin k, ∀ j, ∀ hj : j ≤ logical.top, enumBase+(i.val : ℤ) ∉ (pm.frames j hj).owned)
(hb : st.scalar.core.ptrs 80=enumBase) (hkp : st.scalar.core.ptrs 77=(k : ℤ))
(hf : st.scalar.core.ptrs 20=base) (hE : st.scalar.core.ptrs 53=epoch)
(hOff : st.scalar.core.ptrs 83=(offset : ℤ))
(hbRecords : ∀ i : Fin k, st.scalar.core.mem (vertexRecordAddress (16*(ell+3)) (e i).val offset)=b (e i))
(hbound : ∀ v : Fin n, st.scalar.integerMemory (vertexRecordAddress (16*(ell+3)) v.val 7) ≤ epoch) :
let capacity := k+∑ i : Fin k, (g.neighbors (e i)).length
let answerBase := base+3*(capacity : ℤ)+(k : ℤ)
∃ steps out, ∃ memory : RecursiveMachineMemory g s α ε ell length logical out,
MachineEval m g ω cachedPrincipalSolveCode st steps out ∧
steps ≤ (24*(16*(ell+3))+100)*capacity+29 ∧
SolveIterationBuffers memory enumBase answerBase e (solveOn g α (Finset.univ.image e) b) ∧
memory.queueMass=pm.queueMass ∧ SolveBufferLayout out.scalar base k capacity ∧
out.scalar.core.ptrs 80=enumBase ∧ out.scalar.core.ptrs 53=epoch+1 ∧
out.work ≤ st.work+((24*(16*(ell+3))+100)*capacity+28 : ℕ)+solveCharge m k (principalEntries g α e).length ∧
out.output=st.output ∧ out.scalar.halted=false ∧
(∀ v : Fin n, out.scalar.integerMemory (vertexRecordAddress (16*(ell+3)) v.val 7) ≤ epoch+1) := by sorry
end NearlyOptimalPPR.Computation