04 solver comparison

%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.11%22%0A%23%20dependencies%20%3D%20%5B%0A%23%20%20%20%20%20%22marimo%3D%3D0.23.13%22%2C%0A%23%20%20%20%20%20%22numpy%3E%3D2.0.0%22%2C%0A%23%20%20%20%20%20%22matplotlib%22%2C%0A%23%20%20%20%20%20%22cvx-linalg%3E%3D0.9.6%22%2C%0A%23%20%20%20%20%20%22nncg%22%2C%0A%23%20%5D%0A%23%0A%23%20%5Btool.uv.sources%5D%0A%23%20nncg%20%3D%20%7B%20path%20%3D%20%22..%2F..%2F..%22%2C%20editable%20%3D%20true%20%7D%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.23.13%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Comparing%20inner%20solvers%3A%20CG%2C%20Jacobi%2C%20Nystr%C3%B6m%2C%20GlobalNystrom%0A%0A%20%20%20%20Every%20outer%20active-set%20step%20needs%20one%20free-block%20solve%0A%20%20%20%20%24A_%7BFF%7D%5C%2C%20x_F%20%3D%20b_F%24.%20%60nncg%60%20never%20fixes%20*how*%20that%20solve%20happens%20%E2%80%94%20it%20is%0A%20%20%20%20delegated%20to%20a%20pluggable%20%60InnerSolver%60.%20This%20notebook%20compares%20the%20four%0A%20%20%20%20built-in%20Krylov-based%20choices%20head%20to%20head%2C%20on%20a%20problem%20shaped%20to%20show%0A%20%20%20%20exactly%20what%20each%20buys%20you%3A%0A%0A%20%20%20%20%7C%20solver%20%7C%20preconditioner%20%7C%20cost%20pattern%20%7C%0A%20%20%20%20%7C---%7C---%7C---%7C%0A%20%20%20%20%7C%20%60CG%60%20%7C%20none%20(identity)%20%7C%20pays%20the%20full%20condition%20number%20of%20%24A_%7BFF%7D%24%20%7C%0A%20%20%20%20%7C%20%60Jacobi%60%20%7C%20%24r%20%5Cmapsto%20%5Cmathrm%7Bdiag%7D(A)%5E%7B-1%7D_F%5C%2C%20r%24%20%7C%20strips%20a%20*bad%20diagonal%20scaling*%20%7C%0A%20%20%20%20%7C%20%60Nystrom%60%20%7C%20randomized%20rank-%24r%24%20sketch%20of%20%24A_%7BFF%7D%24%20%7C%20deflates%20a%20few%20eigenvalues%2C%20resketched%20every%20step%20%7C%0A%20%20%20%20%7C%20%60GlobalNystrom%60%20%7C%20same%20sketch%2C%20of%20the%20full%20%24A%24%2C%20masked%20to%20%24F%24%20%7C%20identical%20deflation%2C%20sketched%20once%20ever%20%7C%0A%0A%20%20%20%20%60Nystrom%60%20and%20%60GlobalNystrom%60%20target%20the%20same%20spectral%20structure%20%E2%80%94%20a%0A%20%20%20%20handful%20of%20eigenvalues%20that%20dwarf%20the%20rest%20%E2%80%94%20but%20differ%20in%20*when*%20they%20pay%0A%20%20%20%20for%20the%20sketch.%20%60Nystrom%60%20resketches%20%24A%5BF%2CF%5D%24%20from%20scratch%20on%20every%0A%20%20%20%20outer%20step%3B%20%60GlobalNystrom%60%20sketches%20the%20whole%20operator%20once%20(restricting%0A%20%20%20%20a%20rank-%24r%24%20factorisation%20to%20a%20principal%20submatrix%20is%20exact%2C%20so%20masking%0A%20%20%20%20rows%20of%20one%20global%20basis%20is%20a%20valid%20free-block%20preconditioner%20with%20no%0A%20%20%20%20further%20matrix-free%20products%20against%20%24A%24).%20That%20should%20be%20a%20wash%20on%20a%0A%20%20%20%20single%20solve%20and%20a%20clear%20win%20across%20many.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20time%0A%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20from%20cvx.linalg%20import%20DenseOperator%0A%0A%20%20%20%20from%20nncg%20import%20(%0A%20%20%20%20%20%20%20%20CG%2C%0A%20%20%20%20%20%20%20%20ActiveSetConfig%2C%0A%20%20%20%20%20%20%20%20ActiveSetSolver%2C%0A%20%20%20%20%20%20%20%20GlobalNystrom%2C%0A%20%20%20%20%20%20%20%20Jacobi%2C%0A%20%20%20%20%20%20%20%20Nystrom%2C%0A%20%20%20%20%20%20%20%20NystromConfig%2C%0A%20%20%20%20)%0A%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20ActiveSetConfig%2C%0A%20%20%20%20%20%20%20%20ActiveSetSolver%2C%0A%20%20%20%20%20%20%20%20CG%2C%0A%20%20%20%20%20%20%20%20DenseOperator%2C%0A%20%20%20%20%20%20%20%20GlobalNystrom%2C%0A%20%20%20%20%20%20%20%20Jacobi%2C%0A%20%20%20%20%20%20%20%20Nystrom%2C%0A%20%20%20%20%20%20%20%20NystromConfig%2C%0A%20%20%20%20%20%20%20%20np%2C%0A%20%20%20%20%20%20%20%20plt%2C%0A%20%20%20%20%20%20%20%20time%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20The%20test%20problem%3A%20a%20few%20dominant%20eigenvalues%20over%20a%20spread%20tail%0A%0A%20%20%20%20Neither%20Nystr%C3%B6m%20variant%20helps%20on%20a%20smoothly%20decaying%20spectrum%20%E2%80%94%20there%20is%0A%20%20%20%20nothing%20cheap%20to%20deflate.%20The%20shape%20that%20showcases%20them%20is%20a%20handful%20of%0A%20%20%20%20eigenvalues%20sitting%20far%20above%20a%20spread-out%20tail%3A%20capturing%20just%20those%20few%0A%20%20%20%20directions%20collapses%20the%20condition%20number%20%60Nystrom%60%2F%60GlobalNystrom%60%0A%20%20%20%20actually%20run%20at%20down%20to%20the%20*tail's*%20spread%2C%20while%20plain%20%60CG%60%20still%20pays%0A%20%20%20%20for%20the%20full%20range%20top-to-bottom.%20A%20planted%20optimum%20lets%20us%20check%20every%0A%20%20%20%20solver%20recovers%20the%20same%2C%20correct%20%24x%5E%5Cstar%24.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20def%20make_problem_with_spectrum(n%2C%20n_dominant%2C%20top_gap%2C%20tail_kappa%2C%20support_frac%3D0.5%2C%20seed%3D0)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Planted-optimum%20SPD%20problem%20with%20a%20spectral%20gap.%0A%0A%20%20%20%20%20%20%20%20%60n_dominant%60%20eigenvalues%20sit%20at%20%60top_gap%20*%20tail_kappa%60%20and%20above%2C%20over%20a%0A%20%20%20%20%20%20%20%20geometric%20tail%20spanning%20%60%5B1%2C%20tail_kappa%5D%60.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20rng%20%3D%20np.random.default_rng(seed)%0A%20%20%20%20%20%20%20%20top%20%3D%20tail_kappa%20*%20np.geomspace(top_gap%2C%202.0%2C%20n_dominant)%0A%20%20%20%20%20%20%20%20tail%20%3D%20np.geomspace(1.0%2C%20tail_kappa%2C%20n%20-%20n_dominant)%0A%20%20%20%20%20%20%20%20eig%20%3D%20np.concatenate(%5Btop%2C%20tail%5D)%0A%20%20%20%20%20%20%20%20q%2C%20_%20%3D%20np.linalg.qr(rng.standard_normal((n%2C%20n)))%0A%20%20%20%20%20%20%20%20a%20%3D%20(q%20*%20eig)%20%40%20q.T%0A%20%20%20%20%20%20%20%20a%20%3D%200.5%20*%20(a%20%2B%20a.T)%0A%0A%20%20%20%20%20%20%20%20k%20%3D%20max(1%2C%20round(support_frac%20*%20n))%0A%20%20%20%20%20%20%20%20perm%20%3D%20rng.permutation(n)%0A%20%20%20%20%20%20%20%20supp%20%3D%20perm%5B%3Ak%5D%0A%20%20%20%20%20%20%20%20x_star%20%3D%20np.zeros(n)%0A%20%20%20%20%20%20%20%20x_star%5Bsupp%5D%20%3D%20rng.uniform(0.5%2C%201.5%2C%20size%3Dk)%0A%20%20%20%20%20%20%20%20s_star%20%3D%20np.zeros(n)%0A%20%20%20%20%20%20%20%20s_star%5Bperm%5Bk%3A%5D%5D%20%3D%20rng.uniform(0.5%2C%201.5%2C%20size%3Dn%20-%20k)%0A%20%20%20%20%20%20%20%20b%20%3D%20a%20%40%20x_star%20-%20s_star%0A%20%20%20%20%20%20%20%20return%20a%2C%20b%2C%20x_star%0A%0A%20%20%20%20return%20(make_problem_with_spectrum%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20n_slider%20%3D%20mo.ui.slider(50%2C%20800%2C%20value%3D300%2C%20step%3D10%2C%20label%3D%22dimension%20%24n%24%22)%0A%20%20%20%20n_dom_slider%20%3D%20mo.ui.slider(1%2C%208%2C%20value%3D3%2C%20step%3D1%2C%20label%3D%22%23%20dominant%20eigenvalues%22)%0A%20%20%20%20top_gap_slider%20%3D%20mo.ui.slider(10%2C%201000%2C%20value%3D100%2C%20step%3D10%2C%20label%3D%22dominant%20%2F%20tail%20gap%22)%0A%20%20%20%20tail_kappa_slider%20%3D%20mo.ui.slider(1%2C%204%2C%20value%3D2%2C%20step%3D1%2C%20label%3Dr%22tail%20spread%20%24%5Clog_%7B10%7D%5Ckappa%24%22)%0A%20%20%20%20rank_slider%20%3D%20mo.ui.slider(1%2C%2010%2C%20value%3D4%2C%20step%3D1%2C%20label%3D%22sketch%20rank%22)%0A%20%20%20%20seed_slider%20%3D%20mo.ui.slider(0%2C%2030%2C%20value%3D0%2C%20step%3D1%2C%20label%3D%22seed%22)%0A%20%20%20%20mo.vstack(%5Bn_slider%2C%20n_dom_slider%2C%20top_gap_slider%2C%20tail_kappa_slider%2C%20rank_slider%2C%20seed_slider%5D)%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20n_dom_slider%2C%0A%20%20%20%20%20%20%20%20n_slider%2C%0A%20%20%20%20%20%20%20%20rank_slider%2C%0A%20%20%20%20%20%20%20%20seed_slider%2C%0A%20%20%20%20%20%20%20%20tail_kappa_slider%2C%0A%20%20%20%20%20%20%20%20top_gap_slider%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20make_problem_with_spectrum%2C%0A%20%20%20%20n_dom_slider%2C%0A%20%20%20%20n_slider%2C%0A%20%20%20%20seed_slider%2C%0A%20%20%20%20tail_kappa_slider%2C%0A%20%20%20%20top_gap_slider%2C%0A)%3A%0A%20%20%20%20a%2C%20b%2C%20x_star%20%3D%20make_problem_with_spectrum(%0A%20%20%20%20%20%20%20%20n%3Dn_slider.value%2C%0A%20%20%20%20%20%20%20%20n_dominant%3Dn_dom_slider.value%2C%0A%20%20%20%20%20%20%20%20top_gap%3Dtop_gap_slider.value%2C%0A%20%20%20%20%20%20%20%20tail_kappa%3D10.0**tail_kappa_slider.value%2C%0A%20%20%20%20%20%20%20%20seed%3Dseed_slider.value%2C%0A%20%20%20%20)%0A%20%20%20%20return%20a%2C%20b%2C%20x_star%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20ActiveSetConfig%2C%0A%20%20%20%20ActiveSetSolver%2C%0A%20%20%20%20CG%2C%0A%20%20%20%20DenseOperator%2C%0A%20%20%20%20GlobalNystrom%2C%0A%20%20%20%20Jacobi%2C%0A%20%20%20%20Nystrom%2C%0A%20%20%20%20NystromConfig%2C%0A%20%20%20%20a%2C%0A%20%20%20%20b%2C%0A%20%20%20%20np%2C%0A%20%20%20%20rank_slider%2C%0A%20%20%20%20time%2C%0A%20%20%20%20x_star%2C%0A)%3A%0A%20%20%20%20_op%20%3D%20DenseOperator(a)%0A%20%20%20%20_cfg%20%3D%20ActiveSetConfig(tol%3D1e-8)%0A%20%20%20%20_rank%20%3D%20rank_slider.value%0A%0A%20%20%20%20solvers%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%22CG%20(no%20preconditioner)%22%3A%20CG()%2C%0A%20%20%20%20%20%20%20%20%22Jacobi%22%3A%20Jacobi()%2C%0A%20%20%20%20%20%20%20%20%22Nystrom%20(resketched%20per%20step)%22%3A%20Nystrom(nystrom%3DNystromConfig(rank%3D_rank%2C%20seed%3D0))%2C%0A%20%20%20%20%20%20%20%20%22GlobalNystrom%20(sketched%20once)%22%3A%20GlobalNystrom(nystrom%3DNystromConfig(rank%3D_rank%2C%20seed%3D0))%2C%0A%20%20%20%20%7D%0A%0A%20%20%20%20results%20%3D%20%7B%7D%0A%20%20%20%20for%20_name%2C%20_inner%20in%20solvers.items()%3A%0A%20%20%20%20%20%20%20%20_t0%20%3D%20time.perf_counter()%0A%20%20%20%20%20%20%20%20_res%20%3D%20ActiveSetSolver(inner%3D_inner%2C%20config%3D_cfg).solve(_op%2C%20b)%0A%20%20%20%20%20%20%20%20_dt%20%3D%20time.perf_counter()%20-%20_t0%0A%20%20%20%20%20%20%20%20results%5B_name%5D%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22outer%22%3A%20_res.outer%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22inner%22%3A%20_res.inner%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22time_ms%22%3A%20_dt%20*%201e3%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22error%22%3A%20float(np.max(np.abs(_res.x%20-%20x_star)))%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22converged%22%3A%20_res.converged%2C%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20return%20(results%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo%2C%20results)%3A%0A%20%20%20%20_rows%20%3D%20%22%5Cn%22.join(%0A%20%20%20%20%20%20%20%20f%22%7C%20%7Bname%7D%20%7C%20%7Br%5B'outer'%5D%7D%20%7C%20%7Br%5B'inner'%5D%7D%20%7C%20%7Br%5B'time_ms'%5D%3A.2f%7D%20%7C%20%7Br%5B'error'%5D%3A.2e%7D%20%7C%20%7Br%5B'converged'%5D%7D%20%7C%22%0A%20%20%20%20%20%20%20%20for%20name%2C%20r%20in%20results.items()%0A%20%20%20%20)%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20f%22%22%22%0A%20%20%20%20%20%20%20%20%7C%20solver%20%7C%20outer%20steps%20%7C%20total%20inner%20CG%20iters%20%7C%20wall%20time%20(ms)%20%7C%20max%20error%20vs%20%24x%5E%5C%5Cstar%24%20%7C%20converged%20%7C%0A%20%20%20%20%20%20%20%20%7C---%7C---%7C---%7C---%7C---%7C---%7C%0A%20%20%20%20%20%20%20%20%7B_rows%7D%0A%0A%20%20%20%20%20%20%20%20All%20four%20reach%20the%20same%20planted%20optimum%20(the%20outer%20trajectory%20only%20depends%0A%20%20%20%20%20%20%20%20on%20the%20violator%20tests%2C%20not%20on%20how%20accurately%20the%20inner%20solve%20runs)%20%E2%80%94%0A%20%20%20%20%20%20%20%20what%20differs%20is%20how%20many%20inner%20CG%20iterations%20it%20took%20to%20get%20there%2C%20and%20how%0A%20%20%20%20%20%20%20%20long%20that%20took%20in%20wall%20time.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(plt%2C%20results)%3A%0A%20%20%20%20_names%20%3D%20list(results.keys())%0A%20%20%20%20_inner_counts%20%3D%20%5Bresults%5Bn%5D%5B%22inner%22%5D%20for%20n%20in%20_names%5D%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(8%2C%204))%0A%20%20%20%20_bars%20%3D%20_ax.barh(_names%2C%20_inner_counts%2C%20color%3D%5B%22%23888%22%2C%20%22%235b8%22%2C%20%22%2358b%22%2C%20%22%23b58%22%5D)%0A%20%20%20%20_ax.set_xlabel(%22total%20inner%20CG%20iterations%20(lower%20is%20better)%22)%0A%20%20%20%20_ax.set_title(%22Inner%20iteration%20count%20by%20preconditioner%22)%0A%20%20%20%20_ax.bar_label(_bars%2C%20fmt%3D%22%25d%22%2C%20padding%3D3)%0A%20%20%20%20_ax.invert_yaxis()%0A%20%20%20%20_fig.tight_layout()%0A%20%20%20%20_fig%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Where%20%60GlobalNystrom%60%20actually%20wins%3A%20reusing%20one%20operator%0A%0A%20%20%20%20A%20single%20solve%20is%20close%20to%20a%20wash%3A%20%60GlobalNystrom%60's%20one-time%20sketch%20of%0A%20%20%20%20the%20*full*%20operator%20is%20more%20expensive%20than%20%60Nystrom%60's%20first%20sketch%20of%20a%0A%20%20%20%20(usually%20smaller)%20free%20block%2C%20even%20though%20it%20is%20never%20paid%20again.%20The%0A%20%20%20%20difference%20shows%20up%20once%20the%20*same*%20operator%20is%20solved%20repeatedly%20%E2%80%94%20a%0A%20%20%20%20parameter%20sweep%2C%20successive%20warm%20starts%2C%20a%20sensitivity%20analysis.%20%60Nystrom%60%0A%20%20%20%20pays%20its%20sketch%20cost%20on%20every%20outer%20step%20of%20every%20solve%3B%20%60GlobalNystrom%60%0A%20%20%20%20pays%20it%20once%2C%20ever%2C%20and%20every%20later%20solve%20only%20pays%20the%20cheap%0A%20%20%20%20%24O(%7CF%7C%5C%2C%5Cmathrm%7Brank%7D)%24%20masking%20cost.%0A%0A%20%20%20%20The%20slider%20below%20repeats%20the%20*same*%20operator%20%60A%60%20across%20many%20independent%0A%20%20%20%20right-hand%20sides%2C%20sharing%20one%20solver%20instance%20(and%20hence%2C%20for%0A%20%20%20%20%60GlobalNystrom%60%2C%20one%20cached%20sketch)%20across%20all%20of%20them.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20n_solves_slider%20%3D%20mo.ui.slider(2%2C%2040%2C%20value%3D15%2C%20step%3D1%2C%20label%3D%22number%20of%20right-hand%20sides%22)%0A%20%20%20%20n_solves_slider%0A%20%20%20%20return%20(n_solves_slider%2C)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20ActiveSetConfig%2C%0A%20%20%20%20ActiveSetSolver%2C%0A%20%20%20%20GlobalNystrom%2C%0A%20%20%20%20Nystrom%2C%0A%20%20%20%20NystromConfig%2C%0A%20%20%20%20a%2C%0A%20%20%20%20n_slider%2C%0A%20%20%20%20n_solves_slider%2C%0A%20%20%20%20np%2C%0A%20%20%20%20rank_slider%2C%0A%20%20%20%20time%2C%0A)%3A%0A%20%20%20%20from%20cvx.linalg%20import%20DenseOperator%20as%20_DenseOperator%0A%0A%20%20%20%20_op%20%3D%20_DenseOperator(a)%0A%20%20%20%20_cfg%20%3D%20ActiveSetConfig(tol%3D1e-8)%0A%20%20%20%20_rank%20%3D%20rank_slider.value%0A%20%20%20%20_rng%20%3D%20np.random.default_rng(1)%0A%20%20%20%20_rhs%20%3D%20%5B_rng.standard_normal(n_slider.value)%20for%20_%20in%20range(n_solves_slider.value)%5D%0A%0A%20%20%20%20reuse_results%20%3D%20%7B%7D%0A%20%20%20%20for%20_label%2C%20_inner%20in%20(%0A%20%20%20%20%20%20%20%20(%22Nystrom%20(resketched%20every%20solve)%22%2C%20Nystrom(nystrom%3DNystromConfig(rank%3D_rank%2C%20seed%3D0)))%2C%0A%20%20%20%20%20%20%20%20(%22GlobalNystrom%20(sketched%20once%2C%20shared)%22%2C%20GlobalNystrom(nystrom%3DNystromConfig(rank%3D_rank%2C%20seed%3D0)))%2C%0A%20%20%20%20)%3A%0A%20%20%20%20%20%20%20%20_cumulative%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20_t0%20%3D%20time.perf_counter()%0A%20%20%20%20%20%20%20%20for%20_b%20in%20_rhs%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ActiveSetSolver(inner%3D_inner%2C%20config%3D_cfg).solve(_op%2C%20_b)%0A%20%20%20%20%20%20%20%20%20%20%20%20_cumulative.append((time.perf_counter()%20-%20_t0)%20*%201e3)%0A%20%20%20%20%20%20%20%20reuse_results%5B_label%5D%20%3D%20_cumulative%0A%20%20%20%20return%20(reuse_results%2C)%0A%0A%0A%40app.cell%0Adef%20_(plt%2C%20reuse_results)%3A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(8%2C%204))%0A%20%20%20%20for%20_label%2C%20_cumulative%20in%20reuse_results.items()%3A%0A%20%20%20%20%20%20%20%20_ax.plot(range(1%2C%20len(_cumulative)%20%2B%201)%2C%20_cumulative%2C%20marker%3D%22o%22%2C%20label%3D_label)%0A%20%20%20%20_ax.set_xlabel(%22right-hand%20side%20%23%22)%0A%20%20%20%20_ax.set_ylabel(%22cumulative%20wall%20time%20(ms)%22)%0A%20%20%20%20_ax.set_title(%22Cumulative%20cost%20of%20solving%20the%20same%20operator%20repeatedly%22)%0A%20%20%20%20_ax.legend()%0A%20%20%20%20_fig.tight_layout()%0A%20%20%20%20_fig%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%60GlobalNystrom%60's%20line%20should%20start%20with%20a%20one-time%20bump%20(the%20full-operator%0A%20%20%20%20sketch%2C%20paid%20on%20the%20first%20right-hand%20side)%20and%20then%20grow%20in%20step%20with%0A%20%20%20%20%60Nystrom%60's%20per-block%20resketching%20cost%20%E2%80%94%20flattening%20the%20gap%20between%20them%20as%0A%20%20%20%20more%20right-hand%20sides%20are%20solved.%20On%20a%20single%2C%20one-off%20solve%20there%20is%0A%20%20%20%20little%20reason%20to%20prefer%20%60GlobalNystrom%60%20over%20%60Nystrom%60%3B%20the%20moment%20the%0A%20%20%20%20*same*%20operator%20is%20reused%2C%20the%20sketch-once%20design%20starts%20paying%20for%0A%20%20%20%20itself.%0A%0A%20%20%20%20%23%23%23%20Where%20to%20go%20next%0A%0A%20%20%20%20-%20**%5BActive-set%20methods%5D(01_active_set_methods.html)**%20%E2%80%94%20the%20outer%20loop%0A%20%20%20%20%20%20both%20solvers%20plug%20into.%0A%20%20%20%20-%20**%5BEquality%20constraints%5D(02_equality_constraints.html)**%20%E2%80%94%20the%0A%20%20%20%20%20%20Schur-complement%20path%2C%20where%20every%20outer%20step%20needs%20%24p%2B1%24%20free-block%0A%20%20%20%20%20%20solves%20and%20the%20sketch-once%20saving%20compounds%20further.%0A%20%20%20%20-%20**%5BTest%20problems%5D(03_test_problems.html)**%20%E2%80%94%20the%20planted-optimum%0A%20%20%20%20%20%20generators%20this%20notebook's%20problem%20builder%20is%20modelled%20on.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A