{"id":"906d977e-c8bd-4013-86b7-b9150dd90a4c","arxiv_id":"1908.08901","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Randomized, one-point-per-triangle quadrature assembles finite element systems for rough-coefficient elliptic equations with proven first-order convergence, and an importance-sampling variant reaches nearly second order for smooth data.","lead":"This paper proves convergence rates for finite element discretizations of elliptic equations whose stiffness matrix and load vector are assembled with randomized quadrature, using one random point per mesh triangle. It shows the method handles singular forcing terms that break standard deterministic quadrature, and adds an importance-sampling variant with faster observed convergence.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Stiffness-matrix rate in Theorem 3.5 requires W^{s,q}, s>0, q>2; the motivating L^\\infty coefficient case and the numerical experiments (only \\sigma=1) leave the central claim extrapolated rather than demonstrated.","rationale":"The paper is a serious numerical analysis contribution: the randomized quadrature estimators are well-defined, the proofs are lengthy and mostly self-contained, and the importance-sampling variant is a genuine contribution. The main theorems are conditional on explicit regularity assumptions; I found no clear counterexample to Theorem 3.5 as stated. The reader's weakest assumption points to the same vulnerability I consider load-bearing: the stiffness-matrix error analysis requires \\sigma to have positive fractional Sobolev regularity, while the stated motivation is the L^\\infty regime where deterministic point-evaluation quadrature is unreliable, and Section 6 only exercises \\sigma=1. This gap is not a proof error, but it means the headline 'randomized quadrature for irregular coefficients' is an extrapolation from the proven statements. The secondary issues noted by the reader (the s=1 border case left to the reader, the s=0 border case of Theorem 4.5, and the constant mismatch between Lemma 4.1 and its proof) are minor and do not alter the assessment. A numerical experiment with a genuinely discontinuous \\sigma would directly show whether the W^{s,q} assumption is essential or merely an artifact of the proof technique, so the conditional verdict is appropriate and no change to the reader's judgment is needed.","tokens_in":32092,"tokens_out":22981,"duration_ms":243529,"concrete_test":"Run the randomized stiffness assembly on a test problem with a discontinuous coefficient \\sigma=1+\\alpha 1_A, where A is a union of triangles in the same triangulation (so \\sigma\\in L^\\infty but \\sigma\\notin W^{s,q} for any s>0), with the exact forcing f chosen smooth so only the stiffness quadrature is active. For h=2^{-n}, n=2,...,8, and M=10^4 independent realizations, estimate \\|u^{MC}_h - u_h\\|_{L^2(\\Omega;H^1_0(D))} against the exact-stiffness FEM solution u_h and fit the rate. If the error fails to decay (or decays at a rate below h), the W^{s,q} restriction in Theorem 3.5 is essential and the motivating L^\\infty claim is unsupported; if it decays at first order, the theorem is suboptimal and the gap is only in the proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that randomized quadrature can replace deterministic quadrature in FEM assembly for irregular coefficients is only proven for \\sigma\\in L^\\infty\\cap W^{s,q}(D) with s\\in(0,1], q>2 (Theorem 3.5). For \\sigma\\in L^\\infty only, the proof of the stiffness-matrix term E_2 around Eq. (31) has no estimate: the factor (\\sum_T |T|^{-2} E[(\\int_T\\sigma dx - |T|\\sigma(Z_T))^2 |\\nabla R_h u|^2])^{1/2} is only O(1), not O(h^s), without fractional regularity. Since the paper motivates exactly the L^\\infty regime where deterministic barycentric quadrature fails, and since Section 6 experiments all set \\sigma\\equiv 1, neither the rate nor the necessity of the W^{s,q} assumption for the randomized stiffness assembly is tested. Moreover, for s<1 the term h^s dominates h, so the advertised 'first-order' behavior is not what Theorem 3.5 delivers; the total rate is min(h, h^s, h^{1-2/p}). This is a scope gap rather than an internal contradiction, but it is the load-bearing condition for the headline application.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies randomized quadrature in finite element assembly for the model problem -div(σ∇u)=f with piecewise-linear conforming finite elements on quasi-uniform triangulations in two dimensions. It introduces a stratified Monte Carlo quadrature rule (18) with one independent uniform point per triangle for both the stiffness matrix and the load vector, and an importance-sampling variant (35) for the load vector in the Poisson case. The main theorem (Theorem 3.5) gives an L2(Ω;H1_0) error bound of order O(h||u||_{H2} + h^s |σ|_{W^{s,q}}||u||_{H2} + h^{1-2/p}||f||_{Lp}) under σ ∈ L∞ ∩ W^{s,q}, s ∈ (0,1], q > 2, f ∈ L^p, together with log-weighted variants. Theorems 4.4 and 4.5 provide error estimates for the importance-sampling method in the H1 and L2 norms, Section 5 gives implementation details using a reference triangle and rejection sampling, and Section 6 reports numerical experiments for the Poisson equation with singular and smooth forcing terms.","tokens_in":32325,"tokens_out":18160,"duration_ms":178880,"significance":"If the results hold, the paper provides a detailed, parameter-free analysis showing that randomized quadrature can replace deterministic quadrature in finite element assembly for coefficients that are not continuous, with explicit convergence rates depending on the regularity of σ and f. The proofs are carried out in full detail for the main cases, no fitted constants appear, and the unbiasedness of both estimators is established. The comparison with the deterministic barycentric rule for a singular forcing term is informative and demonstrates a practical advantage. The main caveat is that the central stiffness-matrix estimate requires fractional Sobolev regularity of σ and the numerical experiments do not exercise the stiffness quadrature at all, since they all set σ ≡ 1.","major_comments":[{"comment":"The central error bound for the stiffness matrix requires σ ∈ W^{s,q}(D) with s > 0 and q > 2. For σ ∈ L∞(D) only, the second term in (31) is only O(1): the factor |T|^{-1}∫_T (σ(x)-σ(z))^2 dx is bounded by a constant independent of h when σ has no fractional regularity, so the assembled stiffness matrix is not shown to converge as h → 0. Since the introduction motivates the method for 'general σ ∈ L∞(D)' and for irregular coefficients, the proven result covers a narrower class than the motivation. Please state this limitation prominently, and clarify whether the W^{s,q} condition is believed necessary for a positive rate for the stiffness term.","section":"Section 3, Theorem 3.5 and Eq. (31)"},{"comment":"All numerical experiments set σ ≡ 1, so the randomized stiffness quadrature in Step 5 of Algorithm 1 is never exercised. The observed rates therefore validate only the load-vector quadrature, and the term h^s |σ|_{W^{s,q}} in Theorem 3.5 is not tested. Please add experiments with a rough, non-continuous coefficient in W^{s,q} (for example, a piecewise-constant or oscillatory σ) and report the H1 error against the predicted rate, so that the main claim about irregular coefficients is supported numerically.","section":"Section 6, Figures 2 and 3, Table 1"},{"comment":"The border case s = 1 is dismissed with 'the details are left to the reader.' This case is part of the theorem and is the one that yields the first-order term h||u||_{H2}; please provide the Poincaré–Wirtinger argument in full or as a lemma rather than deferring it.","section":"Theorem 3.5, end of proof"},{"comment":"The border case s = 0 is likewise left to the reader with 'proven analogously.' Since Theorem 4.5 is a main result for the L2 norm, please include the s = 0 argument explicitly, or state and prove the required L2-load-error bound used in the Nitsche trick.","section":"Theorem 4.5, final line"}],"minor_comments":[{"comment":"The constant 1/(4√12) in the statement does not match the constant obtained in the proof around (38), which gives a factor of order 1/√(2√3). Please align the constants or indicate that the stated constant is a more conservative bound.","section":"Lemma 4.1, second assertion"},{"comment":"There is a typo in the last sentence: 'boarder case' should read 'border case.'","section":"Theorem 4.5, proof"},{"comment":"The sentence stating that the randomized quadrature formula is 'convergent at least with order 1' refers to the quadrature estimator itself, not to the finite-element solution error. To avoid confusion, please add a sentence clarifying that the solution error in Theorem 3.5 has the combined rate min(h, h^s, h^{1-2/p}) and is first-order only in the special cases s = 1 and p = ∞.","section":"Introduction, paragraph before (18)"},{"comment":"The paper would benefit from a short comment on the compatibility of Assumption 2.1 (u ∈ H2) with the coefficient class W^{s,q} for s < 1; the cited sufficient condition for Assumption 2.1 is a Lipschitz coefficient, which is stronger than W^{s,q} for s < 1.","section":"Assumption 2.1 and Theorem 3.5"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the scope of the journal and the mathematics appears sound under the stated assumptions. My main concern is the gap between the motivating L∞ coefficient case and the W^{s,q} theorem, together with the absence of numerical experiments that exercise the randomized stiffness assembly. These issues are fixable within the manuscript's scope, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. This is a careful, useful paper on randomized quadrature for FEM assembly, and its headline convergence result is a bit narrower than the motivation suggests. The genuinely new pieces are the detailed error analysis of Haber-style stratified Monte Carlo for stiffness and load assembly of elliptic problems, and a basis-adapted importance-sampling estimator for the load vector. The main theorem is honest: for sigma in L^\\infty \\cap W^{s,q}, s in (0,1], q in (2,\\infty), and f in L^p, the solution converges in L^2(Omega;H^1_0) at rate min(h, h^s, h^{1-2/p}). So first order only when s >= 1; for s < 1 the h^s term dominates, which the authors state plainly. The IS estimator for the Poisson equation is sensible, and Theorem 4.5's h^{1+s} L^2 rate matches the numerics.\n\nCredit where due: no fitted parameters, assumptions are spelled out, and the self-citations are only for standard measurability lemmas. The experiments genuinely show the randomized load assembly handling a singular forcing term where barycentric quadrature blows up. The implementation section is practical and the algorithm stays sparse.\n\nSoft spots, in order. First, and this is the important one: the stiffness-matrix rate requires sigma in W^{s,q} with s > 0 and q > 2. For merely L^\\infty sigma, which is exactly the \"irregular coefficient\" regime the introduction motivates, the proof of the key term (31) only gives O(1); the method is still unbiased but no convergence rate follows. Section 6 never tests a nonconstant sigma, so the load-bearing condition is neither demonstrated nor numerically probed. The stress-test note gets this right. This is a scope gap, not an internal contradiction, but it should decide how the paper is advertised. Second, the s = 1 border case in Theorem 3.5 and the s = 0 border case in Theorem 4.5 are left to the reader. For main theorems, that is sloppy; the arguments are likely routine but they are still missing. Third, Lemma 4.1 states a constant that does not match the constant in its proof, which is minor but should be fixed.\n\nWho this is for: people working on randomized quadrature, numerical methods for PDEs with rough data, and UQ. It deserves a serious referee; the issues are addressable in revision and the central analysis holds up. I'd send it to a numerical-analysis journal and would cite it if I worked in randomized FEM.","headline":"Solid, honest randomized-quadrature FEM analysis; the stiffness-matrix rate needs W^{s,q} regularity that the motivating L^\\infty case doesn't get, but the core is sound and worth refereeing.","tokens_in":32857,"tokens_out":2798,"would_cite":true,"duration_ms":29027,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65C05","65D32","65N15","65N30"],"pacs":[],"model":"deepseek-v4-flash","headline":"Randomized quadrature preserves first-order FEM convergence for elliptic problems with rough coefficients.","keywords":["finite element method","Monte Carlo quadrature","randomized quadrature","elliptic equations","irregular coefficients","stratified sampling","importance sampling","error analysis"],"falsifier":"Take a coefficient σ that is bounded away from zero and infinity but belongs to no $W^{{s,q}}$ with s>0 (for instance, the indicator of a set with fractal boundary), assemble the randomized FEM on a sequence of uniform triangulations, and measure the $L^{2}$(Ω;$H^{1}$) error against the true solution. If the error does not decay as h→0, or decays at a rate strictly worse than first order, the paper's implied robustness of the method for all L^∞ coefficients would be contradicted.","tokens_in":31860,"feed_emoji":"🎲","tokens_out":6772,"duration_ms":62846,"temperature":0.7,"pith_summary":"The paper establishes that the stiffness matrix and load vector of a finite element discretization can be assembled by randomized quadrature — one uniformly random point per mesh triangle — and the resulting random solution still converges to the exact solution at first order in the mesh size h, measured in the root-mean-square $H^{1}$ norm. The central rate is proved in Theorem 3.5 for σ in L^∞∩$W^{{s,q}}$, s∈(0,1], q>2, and f∈L^p, p∈[2,∞]. This matters because deterministic quadrature rules evaluate coefficients at fixed points and can become useless when coefficients or forcing terms are singular or discontinuous; the paper's own experiments show barycentric quadrature producing errors of order $10^{5}$ on a singular forcing term, while the randomized method converges. The paper also designs an importance-sampling estimator for the load vector that is unbiased and achieves higher order for smooth data, and provides implementation details via a reference-triangle transformation and rejection sampling.","feed_headline":"Random quadrature preserves FEM's first-order convergence","feed_subtitle":"One random sample per mesh triangle assembles the system stably even when coefficients or forcing terms are singular.","key_machinery":"The stratified Monte Carlo quadrature $Q^{MC}[v]=\\sum_{T\\in\\mathcal T_h} |T|\\,v(Z_T)$ with $Z_T\\sim U(T)$ independent across triangles. It is unbiased for every $v\\in L^1(D)$, and its mean-square error is bounded by $(\\sqrt{3}/2) h^2 \\|v\\|_{L^2}^2$ via Weitzenböck's triangle-area inequality $|T|\\le (\\sqrt{3}/4)h^2$. Because gradients of piecewise-linear finite element functions are constant on each triangle, the randomized bilinear form $a^{MC}$ remains coercive and bounded pathwise, so each realization is a well-posed sparse linear system. The error estimate for the load-vector term is obtained by expanding the test function in discrete eigenfunctions and using the eigenvalue growth $\\lambda_j\\sim c j$ together with Gagliardo–Nirenberg and Sobolev-embedding inequalities. The importance-sampling variant samples with density proportional to the basis function $\\phi_j$, reducing variance when the forcing term is irregular and gaining order for smooth f.","core_discovery":"Theorem 3.5 is the paper's central quantitative statement: for σ∈L^∞(D)∩$W^{{s,q}}$(D) with s∈(0,1], q>2, σ≥σ0>0, and f∈L^p(D) with p∈[2,∞), the solution $u_h^{{MC}}$ of the randomized discrete problem satisfies $$\\|u-$u_h^{{MC}}$\\|_{$L^{2}$(\\$\\Omega$;$H^{1}$_0(D))} \\le C h \\|u\\|_{$H^{2}$(D)} + C h^s |\\$\\sigma$|_{$W^{{s,q}}$(D)} \\|u\\|_{$H^{2}$(D)} + C $h^{{1-2/p}}$ \\|f\\|_{L^p(D)},$$ with a log-weighted term replacing the last one when f∈L^∞. In words: taking one independent uniform sample per triangle to evaluate σ and f does not degrade the asymptotic first-order convergence of the piecewise-linear finite element method, provided the coefficient has a little fractional regularity. The proof splits the error into the Ritz projection error and a quadrature error, and controls the latter with a variance estimate and an eigenvalue-decay sum over the discrete Laplacian. For the Poisson case σ≡1, the importance-sampling variant $u_h^{{IS}}$ is unbiased with expectation equal to the standard FEM solution, and Theorem 4.5 gives an $L^{2}$(Ω;$L^{2}$(D)) error of order $h^{{1+s}}$ for f∈$W^{{s,2}}$.","pith_inferences":["The unbiasedness of the estimator for every σ∈L^1 suggests the randomized method may converge for merely L^∞ coefficients too, but the rate—or whether first order persists—is an open question the paper does not answer.","For higher-order finite elements, gradients are no longer piecewise constant, so the stiffness estimator becomes biased; extending the analysis would require bounding the product of coefficient smoothness and trial-function smoothness, likely yielding rates that interpolate between the two.","The one-sample-per-cell method could be combined with adaptive mesh refinement to allocate more samples where the coefficient is rough, giving a natural a posteriori error indicator."],"forward_implications":["Randomized assembly restores first-order convergence for the Galerkin method under minimal integrability assumptions: σ only needs to be bounded and measurable for well-posedness, and the theorem adds only a mild fractional regularity to get the rate.","The per-triangle sampling cost is O(1) per entry, the stiffness matrix stays sparse, and the linear solve is unchanged, so the method drops into existing finite element codes.","Singular or discontinuous forcing terms no longer require adaptive mesh refinement or a priori knowledge of singularity locations for quadrature to be reliable.","For the Poisson case with smooth data, the importance-sampling variant achieves near-second-order convergence in the mean-square H^1 norm, offering a practical speed-up over plain Monte Carlo assembly.","In the Poisson case the randomized solution's expectation coincides with the standard FEM solution, so variance, rather than bias, is the only quadrature-induced error."],"supporting_citations":[{"why":"Introduces the stratified Monte Carlo quadrature idea that the estimator (18) is based on.","marker":"[14]"},{"why":"Supplies the standard finite element error estimates, Ritz projection bounds, and the eigenvalue growth law used in the proof of Lemma 3.4.","marker":"[28]"},{"why":"Provides the quasi-uniformity and inverse-estimate tools used in Assumption 2.2 and in the finite element error analysis.","marker":"[4]"},{"why":"Gives Weitzenböck's inequality, which bounds the area of a triangle in terms of its maximal edge length and drives the h^2 variance estimate in Lemma 3.1.","marker":"[38]"},{"why":"Supplies the maximum-norm estimate (12) for piecewise-linear finite element functions, used repeatedly for the load vector estimates.","marker":"[37]"},{"why":"Gives regularity conditions under which Assumption 2.1 (the strong solution H^2 regularity) holds.","marker":"[13]"},{"why":"Provides the Sobolev embedding theorem used to bound W^{1,2ρ'} norms by the H^2 norm of the exact solution.","marker":"[1]"},{"why":"Supplies the Gagliardo–Nirenberg interpolation inequality used to bound L^{p'} norms of discrete eigenfunctions.","marker":"[33]"},{"why":"Provides the theory of importance sampling and the form of the optimal density, motivating the estimator (35).","marker":"[12]"}],"fun_headline_variants":["Random quadrature preserves FEM's first-order convergence","One random sample per triangle: FEM stays first-order","Rough data? Random quadrature still gives first-order FEM","Single-sample random quadrature keeps FEM error O(h)","Randomized quadrature: no loss of FEM convergence rate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of a first-order rate for the randomized stiffness matrix requires the coefficient σ to lie in a fractional Sobolev space $W^{{s,q}}$(D) with s>0 and q>2; for merely bounded measurable coefficients, which are the 'irregular' case motivating the paper, the theorem provides no convergence rate, and the numerical experiments only test σ≡1, so this condition is neither demonstrated nor tested.","fun_headline_variants_meta":{"raw":{"variants":["Random quadrature preserves FEM's first-order convergence","One random sample per triangle: FEM stays first-order","Rough data? Random quadrature still gives first-order FEM","Single-sample random quadrature keeps FEM error O(h)","Randomized quadrature: no loss of FEM convergence rate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000676,"raw_usage":{"total_tokens":3084,"prompt_tokens":965,"completion_tokens":2119,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":581,"completion_tokens_details":{"reasoning_tokens":2041}},"tokens_in":581,"tokens_out":2119,"duration_ms":15742,"temperature":1.0,"reasoning_tokens":2041,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:27:50.182751+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a coefficient σ that is bounded away from zero and infinity but belongs to no $W^{{s,q}}$ with s>0 (for instance, the indicator of a set with fractal boundary), assemble the randomized FEM on a sequence of uniform triangulations, and measure the $L^{2}$(Ω;$H^{1}$) error against the true solution. If the error does not decay as h→0, or decays at a rate strictly worse than first order, the paper's implied robustness of the method for all L^∞ coefficients would be contradicted.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the stratified Monte Carlo quadrature idea that the estimator (18) is based on."},{"cited_title":"Larsson and V","cited_arxiv_id":null,"evidence_quote":"Supplies the standard finite element error estimates, Ritz projection bounds, and the eigenvalue growth law used in the proof of Lemma 3.4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the quasi-uniformity and inverse-estimate tools used in Assumption 2.2 and in the finite element error analysis."},{"cited_title":"Weitzenb¨ ock.¨Uber eine Ungleichung in der Dreieckgsgeometrie","cited_arxiv_id":null,"evidence_quote":"Gives Weitzenböck's inequality, which bounds the area of a triangle in terms of its maximal edge length and drives the h^2 variance estimate in Lemma 3.1."},{"cited_title":"Thom´ ee.Galerkin Finite Element Methods for Parabolic Problems , volume 25 of Springer Series in Computational Mathematics","cited_arxiv_id":null,"evidence_quote":"Supplies the maximum-norm estimate (12) for piecewise-linear finite element functions, used repeatedly for the load vector estimates."},{"cited_title":"Grisvard","cited_arxiv_id":null,"evidence_quote":"Gives regularity conditions under which Assumption 2.1 (the strong solution H^2 regularity) holds."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Sobolev embedding theorem used to bound W^{1,2ρ'} norms by the H^2 norm of the exact solution."},{"cited_title":"Roub´ ıˇ cek.Nonlinear Partial Differential Equations with Applications , volume 153 of In- ternational Series of Numerical Mathematics","cited_arxiv_id":null,"evidence_quote":"Supplies the Gagliardo–Nirenberg interpolation inequality used to bound L^{p'} norms of discrete eigenfunctions."},{"cited_title":"Evans and T","cited_arxiv_id":null,"evidence_quote":"Provides the theory of importance sampling and the form of the optimal density, motivating the estimator (35)."}],"review_version":1}