{"id":"db745342-6eee-454d-b01a-5e02073119dc","arxiv_id":"2411.14082","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"CKTSO speeds up SPICE circuit simulation by selecting the best matrix ordering and using a pivot-checked fast LU factorization with hybrid parallel triangular solving.","lead":"This paper presents CKTSO, a parallel sparse linear equation solver built specifically for SPICE circuit simulators. It combines better matrix ordering, a pivot-checked fast factorization, and a hybrid parallel triangular solve to speed up simulations on multicore machines.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Re-pivoting cost is modeled only with uniformly random restart rows; real re-pivoting positions and costs are not reported, leaving the headline speedup conditional.","rationale":"The reader's conditional verdict is appropriate and my concern reinforces it rather than overturning it. The paper is transparent about the best-case nature of the headline benchmarks and does include both synthetic re-pivoting tests and real SPICE results, so this is not a case of hidden assumptions. However, the single most load-bearing element of the central performance claim is the frequency and cost of re-pivoting during fast factorization. The synthetic tests model re-pivoting with a uniform random restart row, which is an arbitrary proxy; the real SPICE tests report only re-pivoting counts, not restart positions or tail-factorization time. Because the cost of a restart is strongly nonlinear in the restart row, the same number of re-pivoting iterations could have very different performance impact depending on where they occur. Thus the gap between the best-case speedup and the real-world speedup is not fully characterized. This does not invalidate the paper; it means the conditional verdict should remain, with the specific condition being a demonstrated realistic re-pivoting distribution. The proposed instrumentation test would settle the question directly by comparing empirical restart distributions against the uniform-random model.","tokens_in":21309,"tokens_out":5335,"duration_ms":54245,"concrete_test":"Instrument CKTSO to log, for every re-pivoting event in the Table I OP simulations (circuits with 3-26 re-pivoting iterations), the restart row index r and the time spent in pipelined tail factorization with pivoting versus fast factorization. Then repeat the Fig. 14 synthetic experiment with re-pivoting rows drawn from the empirical restart-row distribution instead of uniform [1,N]. If the resulting 16-thread average speedup versus NICSLU falls by more than 30% relative to the uniform-random case, the paper's general-case performance claims must be restated; if the empirical restarts are late or cheap, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"CKTSO's advertised 5.9x average factorization speedup (Fig. 13) is measured in the no-re-pivoting best case. The only general-case evaluation (Fig. 14) injects re-pivoting at a uniformly random row in [1,N] in 3-10% of runs. In actual circuit simulation, a pivot violation is caused by a changed numerical value at a particular position of the reordered matrix; after fill-reducing ordering, such positions may be systematically early or late in the elimination. The cost of a re-pivot is strongly position-dependent: if the first bad pivot is at row r, the tail factorization with pivoting recomputes roughly the submatrix from r to N according to the ETree, so an early restart can cost almost a full pivoting factorization. Tables I and II report only the number of re-pivoting iterations (3-26), not the restart rows, and not the share of factorization time spent in pipelined tail factorization. The SPICE speedups (2.38x, 2.56x) are therefore not yet decomposed into fast-factorization savings and re-pivoting penalties. If real re-pivoting tends to occur early (e.g., rows corresponding to strongly nonlinear devices surviving the ordering), the amortized speedup could be substantially lower than the best-case figure, and the main performance claim would need to be qualified by workload class.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"CKTSO is a parallel sparse direct solver designed for SPICE-style circuit matrices. Its main technical contributions are a combined minimum-degree/nested-dissection ordering, a \"fast factorization with pivot check\" that reuses a guessed elimination graph and falls back to ETree-scheduled factorization with pivoting when a pivot violation is detected, and a structure-adaptive hybrid parallel triangular solving method. The paper reports benchmark results on 56 SuiteSparse circuit matrices, showing fewer fill-ins and FLOPs than NICSLU and PARDISO, and SPICE operating-point/transient simulations reporting 2.38x and 2.56x average speedups respectively. The central claim is that CKTSO achieves better performance than state-of-the-art solvers for a wide range of circuit matrices.","tokens_in":21487,"tokens_out":6993,"duration_ms":72009,"significance":"If the claims hold, CKTSO represents a meaningful advance for circuit simulation: it directly targets the three known bottlenecks of sparse direct solvers in SPICE, namely ordering quality, parallel factorization scalability, and the notoriously sequential triangular solve. The algorithmic ideas are clearly specified, the evaluation is anchored on external SuiteSparse benchmarks and independent solvers, and the code is released, which are all strengths. The work is not circular: the speedups are measured against external solver implementations, and the fast factorization is a component integrated into a complete solver. However, the evidence is incomplete precisely where it matters for the headline claims: no numerical accuracy or residual comparison is reported, and the general-case re-pivoting evaluation uses a synthetic uniform-random model rather than data from actual circuit simulation iterations.","major_comments":[{"comment":"Numerical accuracy is never reported. The experimental section reports fill-in counts, FLOPs, and timings, but contains no residual norms, forward errors, or convergence-failure data for any of the 56 benchmark matrices. This is load-bearing because the core algorithmic contribution is a fast path that intentionally omits pivoting and replaces it with a pivot check (Section IV, Algorithms 3 and 4). The pivot check in Algorithm 1, lines 6-7, ensures that the chosen pivot is not small relative to the current row, but it does not by itself bound the error of the final solution; a pivoting-free factorization can pass such a check and still lose accuracy. The claim in Section IV that fast factorization has \"numerical stability similar to that of factorization\" is therefore not substantiated. The authors should report max residual norms for CKTSO, NICSLU, and PARDISO on all 56 benchmarks, at least for the no-re-pivoting best case and the 10% re-pivoting general case, and should also report accuracy-related quantities for the SPICE runs in Tables I and II.","section":"Section VI"},{"comment":"The general-case re-pivoting experiment is not representative of circuit workloads. Re-pivoting is injected by randomly selecting 3%, 5%, or 10% of the 100 runs and then choosing the restart row uniformly from [1, N]. In an actual factorization, the restart row is determined by a pivot violation at a particular position of the reordered matrix, and the cost of the pipelined tail factorization depends strongly on that position: an early restart can require nearly a full ETree-scheduled factorization with pivoting, while a late restart is cheap. Tables I and II report only the number of re-pivoting iterations (3 to 26) and not the restart rows or the share of factorization time spent in the tail factorization. The observation in Fig. 14 that speedups drop by only about 20% is therefore not directly transferable to real workloads. This is load-bearing because the headline 5.9x factorization speedup in Fig. 13 is a no-re-pivoting best case, and the amortized speedup in practice depends on re-pivot frequency and position.","section":"Section VI-A2, Fig. 14"},{"comment":"The performance claims in the abstract and conclusions are stated without the qualification that most benchmark speedups are best-case no-re-pivoting measurements. The paper itself notes in Section VI-A2 that \"most benchmark tests correspond to the best case of CKTSO's fast factorization, that is, no re-pivoting happens,\" but this caveat does not appear in the abstract or the conclusions. The SPICE results in Tables I and II are valuable real-workload evidence, but they cover only five nonlinear operating-point circuits and six linear power-grid transient circuits, and they do not decompose the runtime into fast-factorization savings and tail-factorization penalties. Before the \"wide range of circuit matrices\" claim can stand as stated, the paper should either calibrate the re-pivoting model on actual NR iterations for a larger and more diverse set of circuits, or explicitly scope the performance claim to the regime in which re-pivoting is rare.","section":"Abstract and Section VII"}],"minor_comments":[{"comment":"The caption of Fig. 15 says that the legend \"solver-T\" means the factorization time, but the figure compares triangular solving time; this should be corrected.","section":"Fig. 15 caption"},{"comment":"In the contribution list, \"stat-of-the-art solvers\" should be \"state-of-the-art solvers\".","section":"Section I, Contributions"},{"comment":"The sentence \"CKTSO is the fastest for 50 out of the 56 benchmarks\" should specify whether the count applies to the 16-thread CKTSO run or to both the 1-thread and 16-thread configurations, since the surrounding text mixes both comparisons.","section":"Section VI-A2"},{"comment":"Similarly, the statement that CKTSO is the fastest for 49 out of 56 benchmarks in triangular solving should state the thread configuration used for CKTSO in that count.","section":"Section VI-A3"},{"comment":"The sentence \"the setup time is about 2× of a solving time\" is awkward; consider writing \"about twice a single solving time\".","section":"Section V-C"},{"comment":"No variance or run-to-run spread is reported for the 100 repeated factorizations used in the general-case re-pivoting experiment; a standard deviation or min-max range would help the reader assess the stability of the reported averages.","section":"Section VI-A2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript header states that the paper has already been accepted by IEEE TCAD and includes a DOI. If this is being handled as a fresh submission, the editor may wish to clarify the review status. The technical assessment above concerns the manuscript as provided; the main missing evidence is numerical accuracy reporting and a realistic re-pivoting model, both of which are within the scope of a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this is a genuine contribution, not a repackaging. The structure-adaptive hybrid triangular solving is new and gives real measured speedups (1.37–2.89x over sequential NICSLU, 2.3x scaling at 16 threads), and the combined ordering selection does produce fewer fill-ins than either minimum-degree or nested dissection alone across the 56-matrix suite. The fast factorization with pivot check is inherited from the author's ICCAD 2022 paper, and the paper says so. That is honest, and integrating it into a full solver with SPICE integration is a legitimate piece of work.\n\nThe benchmark reporting is mostly transparent: they compare against NICSLU and PARDISO, include ordering-controlled comparisons (NICSLU(o), PARDISO(o)), and report per-matrix results. The SPICE end-to-end numbers (2.38x OP, 2.56x transient) are the strongest evidence—they are actual simulation times, not microbenchmarks.\n\nNow the soft spots, in proportion. The biggest one is that the headline factorization speedup (5.9x vs NICSLU-16) is the no-re-pivoting best case. That is stated in the text, so it is not hidden, but it means the general-case claim is only backed by synthetic re-pivoting tests where the restart row is uniformly random in [1,N]. The stress-test concern is valid: re-pivoting cost is strongly position-dependent, and the real SPICE tables report only the count of re-pivoting iterations (3–26), not where they hit in the elimination. If real re-pivoting tends to occur early, the amortized speedup could be lower than the best-case figure. The paper would be stronger with restart-row data from the actual SPICE runs. That said, the real SPICE speedups are still sizable even with re-pivoting present, so this is a qualification, not a fatal flaw.\n\nTwo smaller gripes. There is no numerical accuracy or residual-error comparison at all, which matters for a solver that skips pivoting by default. And several thresholds (alpha=2.0, 70% density, 300k nonzeros, m=8) are empirical with no sensitivity analysis. Minor, but worth noting.\n\nWho is this for? Anyone working on circuit simulation or sparse direct solvers for EDA. It is a useful, well-scoped contribution, not a paradigm shift. I would bring it to a reading group and would cite it in related work on parallel sparse solvers. It deserves a serious peer review; a referee should push on the re-pivoting characterization and ask for residual checks, but the paper is clearly above the bar.","headline":"A solid, honestly-scoped engineering paper on a parallel sparse solver for SPICE; the new triangular-solving and ordering contributions are real, but the headline speedup rests on the no-re-pivoting best case and the re-pivoting model is synthetic.","tokens_in":22074,"tokens_out":1415,"would_cite":true,"duration_ms":15667,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F05","65F50","65Y05"],"pacs":[],"model":"deepseek-v4-flash","headline":"CKTSO claims a parallel sparse solver for SPICE that beats state-of-the-art solvers on a wide range of circuit matrices.","keywords":["SPICE simulation","sparse linear solver","LU factorization","circuit simulation","parallel computing","triangular solving","elimination graph","nested dissection"],"falsifier":"Run CKTSO on SPICE transient benchmarks with frequent abrupt nonlinear events, such as switching or clamping, and count re-pivot events per factorization. If average re-pivoting substantially exceeds the tested 10% rate, the reported average speedups should fall by about 20% or more; if a large fraction of matrices show re-pivoting in nearly every iteration, CKTSO's fast path reduces to the slower pivoting path and the central speed claim is falsified.","tokens_in":21000,"feed_emoji":"⚡","tokens_out":6000,"duration_ms":54453,"temperature":0.7,"pith_summary":"CKTSO is a parallel sparse linear solver designed for SPICE circuit simulation, and the paper claims it solves matrices faster than existing solvers across a broad range of circuit types. The key insight is that in most simulation iterations the matrix values change only slightly, so the solver can reuse the pivoting order and dependency structure from the previous factorization, schedule work on that \"guessed\" structure, and check pivots as it goes to preserve numerical stability. Alongside this fast factorization, CKTSO combines minimum-degree and nested-dissection orderings to cut fill-ins, and partitions triangular solves into sparse and dense regions that are parallelized differently. If the claims hold, CKTSO would make the linear solver a smaller bottleneck in SPICE, with measured 5.9x average speedup over NICSLU for 16-thread LU factorization and 2.38x and 2.56x speedups in operating-point and transient simulations.","feed_headline":"Circuit solver CKTSO beats NICSLU 5.9x on LU factorization","feed_subtitle":"Combines hybrid ordering, pivot-checked fast LU, and adaptive parallel triangular solving to cut SPICE simulation time.","key_machinery":"The central objects are the elimination graph (EGraph) and elimination tree (ETree). The EGraph encodes exact row-to-row dependencies for a fixed LU structure and is used to schedule fast factorization when that structure is guessed from the previous iteration; the ETree encodes a dependency upper bound that remains valid under any pivoting order and is used to restart factorization when a pivot check fails. A second mechanism is the structure-adaptive triangular partition, which splits the lower and upper triangular factors into a sparse block solved by levelized parallel rows plus a dense bottom-right region subdivided into rectangular slices solved in parallel and triangular pieces solved sequentially.","core_discovery":"The paper's central claim is that a sparse solver can be built specifically for circuit matrices that outperforms state-of-the-art general and circuit-oriented solvers by exploiting two structural facts: circuit matrices have a characteristic nonzero distribution, and values evolve smoothly across Newton-Raphson iterations. On that basis CKTSO proposes a fast LU factorization that assumes the previous EGraph remains valid, checks each pivot, and falls back to elimination-tree-scheduled factorization with pivoting only when a pivot fails; a hybrid ordering that selects the best of minimum-degree and nested dissection; and a triangular solver that splits L and U into sparse, rectangular, and dense triangular blocks solved with different parallel strategies. The experiments show CKTSO fastest for 50 of 56 benchmark matrices in factorization and 49 in triangular solving, with average 16-thread speedups of 5.9x over NICSLU and 11.9x over PARDISO, and 2.38x and 2.56x speedups in operating-point and transient SPICE simulations.","pith_inferences":["Beyond the paper, the guess-the-EGraph-and-check-pivots strategy could apply to any solver embedded in a Newton-like loop where matrices evolve smoothly, such as power-flow or nonlinear PDE time stepping, since a pivot check plus ETree fallback gives it a safety net that plain re-factorization lacks.","Beyond the paper, the triangular partition into a sparse block plus dense rectangular and triangular pieces suggests a natural mapping to heterogeneous hardware: the sparse part needs latency-hiding parallelism, while the dense bottom-right block could be handed to vectorized or GPU kernels.","Beyond the paper, the decisive test is a benchmark of real nonlinear circuits with frequent sharp transients; the paper reports only 3 to 26 re-pivot events in its SPICE tests, so a broader sampling would show how often the smooth-change premise holds in practice."],"forward_implications":["In benchmark tests on 56 circuit matrices, CKTSO's 16-thread fast LU factorization is on average 5.9x faster than NICSLU and 11.9x faster than PARDISO.","For triangular solving, CKTSO is on average 1.37 to 2.89x faster than NICSLU's sequential solving across 1 to 16 threads.","In SPICE operating-point simulations of nonlinear circuits, CKTSO with 16 threads finishes 2.38x faster than NICSLU on average; in transient simulations of linear circuits, it is 2.56x faster.","Because pre-processing runs both minimum-degree and nested-dissection orderings and picks the one with fewer fill-ins, CKTSO produces fewer fill-ins than either method alone: 8.8% fewer than NICSLU and 62.3% fewer than PARDISO on average.","Even in a synthetic general case where 10% of factorization runs require re-pivoting, the speedup over NICSLU drops only about 20%, indicating the fast path survives occasional pivot failures."],"supporting_citations":[{"why":"Proposes the previous fast factorization with pivot check that CKTSO extends into a complete solver.","marker":"[15]"},{"why":"NICSLU is the circuit-oriented solver CKTSO is compared against and the source of the levelization-based scheduling adopted here.","marker":"[6]"},{"why":"Introduces the ETree/EGraph dual-mode scheduling used for parallel factorization and re-factorization.","marker":"[7]"},{"why":"KLU is the sequential sparse left-looking solver whose algorithm and performance anchor the circuit-solver baseline.","marker":"[4]"},{"why":"Gilbert-Peierls sparse partial pivoting is the underlying up-looking/left-looking factorization algorithm that CKTSO and its predecessors build on.","marker":"[5]"},{"why":"Defines the elimination tree dependency upper bound that CKTSO uses to schedule tail factorization after re-pivoting.","marker":"[16]"},{"why":"SuiteSparse Matrix Collection provides the 56 circuit matrices used in the benchmark comparisons.","marker":"[17]"},{"why":"METIS implements the nested dissection used in CKTSO's hybrid ordering and in PARDISO's ordering.","marker":"[31]"},{"why":"Constrained minimum degree orders the diagonal submatrices after incomplete nested dissection, keeping the separator fill-in impact in view.","marker":"[32]"},{"why":"PARDISO is the general-purpose sparse solver used as a second comparison baseline.","marker":"[9]"}],"fun_headline_variants":["CKTSO parallel solver beats NICSLU 5.9x on LU","Circuit solver CKTSO outruns PARDISO 11.9x","CKTSO: sparse solver for faster SPICE simulation","Parallel LU solver CKTSO tops 50 circuit benchmarks","CKTSO cuts SPICE simulation time with adaptive solving"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that circuit simulation matrices change smoothly enough between consecutive Newton-Raphson iterations that the previous pivoting order and LU structure remain valid in the large majority of iterations.","fun_headline_variants_meta":{"raw":{"variants":["CKTSO parallel solver beats NICSLU 5.9x on LU","Circuit solver CKTSO outruns PARDISO 11.9x","CKTSO: sparse solver for faster SPICE simulation","Parallel LU solver CKTSO tops 50 circuit benchmarks","CKTSO cuts SPICE simulation time with adaptive solving"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000181,"raw_usage":{"total_tokens":1311,"prompt_tokens":951,"completion_tokens":360,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":567,"completion_tokens_details":{"reasoning_tokens":269}},"tokens_in":567,"tokens_out":360,"duration_ms":3607,"temperature":1.0,"reasoning_tokens":269,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:32:48.563428+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run CKTSO on SPICE transient benchmarks with frequent abrupt nonlinear events, such as switching or clamping, and count re-pivot events per factorization. If average re-pivoting substantially exceeds the tested 10% rate, the reported average speedups should fall by about 20% or more; if a large fraction of matrices show re-pivoting in nearly every iteration, CKTSO's fast path reduces to the slower pivoting path and the central speed claim is falsified.","supporting_citations":[{"cited_title":"Numerically-Stable and Highly-Scalable Parallel LU Fac- torization for Circuit Simulation,","cited_arxiv_id":null,"evidence_quote":"Proposes the previous fast factorization with pivot check that CKTSO extends into a complete solver."},{"cited_title":"NICSLU: An Adaptive Sparse Matrix Solver for Parallel Circuit Simulation,","cited_arxiv_id":null,"evidence_quote":"NICSLU is the circuit-oriented solver CKTSO is compared against and the source of the levelization-based scheduling adopted here."},{"cited_title":"An EScheduler-Based Data Dependence Analysis and Task Scheduling for Parallel Circuit Simulation,","cited_arxiv_id":null,"evidence_quote":"Introduces the ETree/EGraph dual-mode scheduling used for parallel factorization and re-factorization."},{"cited_title":"Algorithm 907: KLU, A Direct Sparse Solver for Circuit Simulation Problems,","cited_arxiv_id":null,"evidence_quote":"KLU is the sequential sparse left-looking solver whose algorithm and performance anchor the circuit-solver baseline."},{"cited_title":"Sparse partial pivoting in time proportional to arithmetic operations,","cited_arxiv_id":null,"evidence_quote":"Gilbert-Peierls sparse partial pivoting is the underlying up-looking/left-looking factorization algorithm that CKTSO and its predecessors build on."},{"cited_title":"The role of elimination trees in sparse factorization,","cited_arxiv_id":null,"evidence_quote":"Defines the elimination tree dependency upper bound that CKTSO uses to schedule tail factorization after re-pivoting."},{"cited_title":"SuiteSparse Matrix Collection","cited_arxiv_id":null,"evidence_quote":"SuiteSparse Matrix Collection provides the 56 circuit matrices used in the benchmark comparisons."},{"cited_title":"The Minimum Degree Ordering with Constraints,","cited_arxiv_id":null,"evidence_quote":"Constrained minimum degree orders the diagonal submatrices after incomplete nested dissection, keeping the separator fill-in impact in view."},{"cited_title":"Solving unsymmetric sparse systems of linear equations with PARDISO,","cited_arxiv_id":null,"evidence_quote":"PARDISO is the general-purpose sparse solver used as a second comparison baseline."}],"review_version":1}