{"id":"0efcb20c-f06b-4e53-9014-317934dd270d","arxiv_id":"2505.05598","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For nonsymmetric and indefinite two-level solvers, interpolation and restriction built from generalized eigenvectors of (A,M) are proved optimal in a family of norms, with tight convergence factor |1−λ_{nc+1}|^{ν1+ν2}.","lead":"Many linear systems are solved by alternating a cheap smoother with a coarse-grid correction. This paper proves which interpolation and restriction operators give the fastest possible two-level iteration for nonsymmetric and indefinite problems, and verifies the bounds on advection and wave equations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.3's real-valued optimality is false when n_c splits a conjugate eigenvalue pair: the identity range(P♯B_c)=range(W_{r,1:n_c}) fails, and a 2x2 example violates the claimed bound.","rationale":"The complex-valued optimality argument in Theorems 3.3 and 3.5 appears internally consistent under the stated diagonalizability and invertibility assumptions: the transformation to (I-Lambda)^{nu2}(I-Q)(I-Lambda)^{nu1} and the Courant-Fischer lower bound in (3.29) are valid. The reader's diagonalizability caveat is a genuine limitation and is already acknowledged in Remark 5.1, but it is not the most load-bearing issue for the paper's headline claim. The more serious problem is in the real-valued transfer operator construction, a central advertised contribution: the proof of Theorem 4.3 relies on a range identity that is false when the truncation n_c splits a complex-conjugate eigenvalue pair. The 2x2 example above satisfies every stated assumption of the paper yet contradicts the bound in (4.18) and the optimality in (4.19). This is an internal inconsistency, not a disagreement with external consensus, and it is not flagged anywhere in the manuscript. The paper can likely be repaired by restricting n_c so that conjugate pairs are not split, or by giving a separate optimality statement for real coarse spaces of odd dimension in fully complex spectra. Because the flaw is localized and correctable, the appropriate verdict is conditional acceptance with a mandatory revision, rather than outright rejection.","tokens_in":1048,"tokens_out":1021,"duration_ms":318219,"concrete_test":"Run the 2x2 test: M=I, A=[[1,-2],[2,1]], n_c=1, diagonal scaling D=I, nu1=nu2=1. Form W_r and W_l via (4.3), set P_R♯=R_R♯=[1,1]^T, and compute the norm of the two-level error propagation using the norm matrix W_r^{-T}D^2 W_r^{-1}=I/2. Compare the result with |1-lambda_2|^2=4; the computed value sqrt(80) falsifies (4.18)-(4.19). Also check the asserted range equality range(P♯B_c)=range(W_{r,1:1}) directly: the left side is span([i,1]^T), while the right side is span([1,1]^T).","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 4.1 transfers optimality to real operators through the identity range(P_R♯)=range(P♯B_c)=range(W_{r,1:n_c}) in (4.14), with B_c=(T^*)_{cc}. This identity holds only when the first n_c columns of the complex eigenvector basis contain complete conjugate-pair blocks. If n_c splits such a pair, the 2x2 block of T^* couples eigenvectors v_{r,n_c} and v_{r,n_c+1}, so W_{r,1:n_c} is not a coarse-space change of basis of P♯; Lemma 4.2 cannot be invoked, and the claimed optimality in Theorem 4.3(3) is not established and is false as stated. A minimal diagonalizable counterexample is M=I, A=[[1,-2],[2,1]], n_c=1, eigenvalues 1+2i and 1-2i, and diagonal scaling D=I. From (4.3), W_{r,1}=W_{l,1}=[1,1]^T and the norm matrix is (1/2)I, so the norm is the Euclidean norm. With P_R♯=R_R♯=[1,1]^T and nu1=nu2=1, direct computation gives the two-level error norm as sqrt(80) approx 8.944, whereas (4.18) predicts |1-lambda_2|^2=4. The complex optimal operators P=R=[i,1]^T attain 4 in the same norm. The theorem needs an explicit no-split condition or a fundamentally different statement for real coarse spaces whose dimension cuts a conjugate pair.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies algebraic two-level methods for linear systems Ax=b with a fine-space preconditioner M and transfer operators P,R. For a non-Hermitian pencil (A,M), it constructs complex-valued 'optimal' transfer operators P♯ and R♯ whose ranges are spanned by the first n_c right and left generalized eigenvectors, ordered by decreasing |1−λ|. It characterizes all HPD norms in which the resulting coarse-space correction Π(P♯,R♯) is orthogonal (Theorem 3.1), proves that in the N=V_r^{-*}D^*DV_r^{-1} norms the error-propagation norm, spectral radius, and geometrically averaged norm all coincide and equal |1−λ_{n_c+1}|^{ν1+ν2} (Theorem 3.3), and claims that P♯,R♯ minimize the N-norm over all possible transfer operators (Theorem 3.5). It then introduces real-valued generalized eigenvectors W_l,W_r for real A,M and claims that the corresponding real transfer operators P_R♯,R_R♯ satisfy the same convergence bounds and optimality in related real norms (Theorem 4.3). Numerical experiments for advection-reaction and mixed wave-equation discretizations compare the predicted factor |1−λ_{n_c+1}|^{ν1+ν2} with computed convergence factors.","tokens_in":25768,"tokens_out":21417,"duration_ms":214271,"significance":"If the complex-valued results are correct, this is a substantial theoretical contribution: it upgrades the pseudo-optimality of Ali et al. to genuine norm optimality, gives tight norm bounds for nonnormal two-level error propagators, recovers the HPD results of Brannick et al. as a special case, and yields an explicit condition for convergence in the N-norm. The derivations are largely transparent and parameter-free, and the numerical section provides direct verification of the equality in Theorem 3.3. However, the real-valued transfer-operator theorem, which is a central advertised practical contribution, is false as stated when n_c splits a conjugate eigenvalue pair, and the Courant-Fischer theorem used in the optimality proof is misstated. These issues need to be repaired before the paper's main claims can be accepted.","major_comments":[{"comment":"The identity range(P_R♯)=range(P♯B_c)=range(W_{r,1:n_c}) in (4.14) is valid only when n_c does not split a conjugate eigenvalue pair. If n_c cuts a 2×2 block of T^*, then B_c=(T^*)_{cc} is not a complete block of the similarity transformation, so P♯B_c involves only one complex eigenvector of the pair while W_{r,1:n_c} contains a real combination of both; Lemma 4.2 cannot be invoked and Theorem 4.3(3) is not established. A concrete counterexample is M=I, A=[[1,-2],[2,1]], n_c=1, whose eigenvalues are 1±2i. With the construction in (4.3), W_{r,1}=[1,1]^T and \\hat N=(1/2)I, so the \\hat N-norm is the Euclidean norm. Taking P_R♯=R_R♯=[1,1]^T and ν1=ν2=1 gives E_TG=[[-6,-6],[2,2]] and ||E_TG||_{\\hat N}=sqrt(80)≈8.944, while (4.18) predicts |1−λ_2|^2=4; the complex optimal operators P=R=[1,-i]^T attain 4 in the same norm. The theorem therefore needs an explicit no-split condition or a different real-valued optimality statement for coarse spaces whose dimension cuts a conjugate pair.","section":"§4.1, Eq. (4.14), Theorem 4.3(3)"},{"comment":"The generalized Courant-Fischer formula in Theorem 3.4 is misstated: with eigenvalues ordered α_1≤...≤α_n, the minimum over subspaces of dimension n−k+1 equals α_{n−k+1}, not α_k (for n=2 and k=1, the displayed expression is the maximum over the whole space and equals α_2). The proof of Theorem 3.5 uses the displayed formula with dim null(\\hat R^*)=n_f=n−n_c and concludes k=n_c+1, which would give α_{n_c+1}=|1−λ_{n_f}|^{2(ν1+ν2)} rather than the claimed |1−λ_{n_c+1}|^{2(ν1+ν2)}. The intended lower bound can be recovered from the correct min-max statement (the minimum over an n_f-dimensional subspace gives the n_f-th smallest eigenvalue, which is μ_{n_c+1} in the descending ordering μ_i=|1−λ_i|^{2(ν1+ν2)}), but as written the proof is not valid.","section":"§3.3, Theorem 3.4 and Eq. (3.29c)"}],"minor_comments":[{"comment":"In the abstract, 'in the case of that A and M are real valued' should be 'in the case that A and M are real valued'.","section":"Abstract"},{"comment":"The condition d_{i+1}=d_i if λ_{i+1}=λ_i does not enforce the needed equality for a conjugate pair, since λ_{i+1}=\\overline{λ_i}\\neq λ_i; it should state that d_i=d_{i+1} when λ_i and λ_{i+1} form a conjugate pair.","section":"Eq. (4.17)"},{"comment":"There is a typo 'identifty' in the sentence introducing Eq. (3.5).","section":"Proof of Lemma 3.2"},{"comment":"There is a typo 'eignevector matrices' in Remark 5.1.","section":"Remark 5.1"},{"comment":"The sentence in Section 5.4 that |1−λ_{n_c+1}|<1 is necessary 'regardless of the interpolation and restriction used' should be qualified as necessity for contraction in the N-norm; the N-norm lower bound in Corollary 3.7 does not by itself rule out asymptotic convergence in spectral radius for some other P,R.","section":"Section 5.4 and Corollary 3.7"}],"recommendation":"major_revision","confidential_remarks":"I recommend major revision. The complex-valued optimality framework appears sound and interesting, but the real-valued Theorem 4.3 is false as stated when n_c splits a conjugate pair, and the Courant-Fischer theorem in Section 3.3 is misstated. Both issues are load-bearing for the paper's advertised claims and should be fixed before further consideration."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear X,\n\nQuick take: the complex-valued part of this paper is a genuine step forward and looks correct. The real-valued part, however, has a load-bearing bug: Theorem 4.3(3) is false when the coarse dimension cuts a conjugate eigenvalue pair.\n\nWhat's new and good: Section 3 characterizes all inner products in which the coarse-space correction built from the eigenvector-based transfer operators is orthogonal (Theorem 3.1), gives tight N-norm convergence bounds that equal the spectral radius (Theorem 3.3), and proves genuine optimality over all P,R in these norms via a clean Courant-Fischer argument (Theorem 3.5). That upgrades the pseudo-optimality from [5] and recovers the HPD case. The derivations are transparent, and the paper is honest about the diagonalizability assumption (Remark 5.1).\n\nThe soft spot: the transfer of optimality to real operators in Section 4. The identity range(P_R#)=range(P#B_c) in (4.14) only holds when the first n_c complex eigenvectors contain whole conjugate-pair blocks. If n_c splits a pair, W_{r,1:nc} is not a coarse-space change of basis of P#: the real vector mixes two complex eigenvectors, so Lemma 4.2 cannot be invoked. A minimal example (A=[[1,-2],[2,1]], M=I, n_c=1) shows the real operator P_R#=[1,1]^T gives ||E||≈8.94 while the theorem predicts 4, and the complex optimal [i,1]^T attains 4. So Theorem 4.3(3) needs an explicit no-split condition or a different construction (e.g., a 2D real coarse space for the pair).\n\nMinor issue: Corollary 3.7 is phrased as necessary and sufficient for existence of any convergent two-level method. What is actually proven is necessity and sufficiency in the N-norm. Since rho(E) ≤ ||E||_N, the inequality gives no spectral-radius lower bound for arbitrary P,R, so the 'no method can converge' conclusion overreaches unless 'convergent' is explicitly in the N-norm.\n\nBottom line: Sections 2–3 are solid and worth publishing. Section 4 needs real work before the advertised real-valued optimality can be trusted. A serious referee should engage; with the fix, it's a strong paper. I'd send it out.","headline":"Strong complex-valued optimality theory for two-level transfer operators, but the real-valued optimality theorem is false when n_c splits a conjugate eigenvalue pair.","tokens_in":26258,"tokens_out":10170,"would_cite":true,"duration_ms":87982,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65N55","65F10","65F15","65F35","65F50"],"pacs":[],"model":"deepseek-v4-flash","headline":"For nonsymmetric and indefinite systems, the best possible transfer operators in a two-level method are the left and right generalized eigenvectors of the matrix pencil $(A,M)$.","keywords":["two-level methods","algebraic multigrid","optimal transfer operators","nonsymmetric problems","indefinite problems","generalized eigenvalue problems","real-valued transfer operators","convergence bounds"],"falsifier":"Take a small diagonalizable but non-normal pencil, for instance a $3\\times 3$ nonsymmetric $A$ with $M=I$, order the eigenvalues so $n_c=1$, and compute $\\|E_{\\mathrm{TG}}^{(1,1)}(P_\\sharp,R_\\sharp)\\|_N$ with $D=I$. The central claim is wrong if this number differs from $|1-\\lambda_2|^{2}$ or if a specific alternative pair $(P,R)$ gives a smaller $N$-norm. A boundary check: unstabilized upwind DG advection produces a non-diagonalizable $M^{-1}A$, so the assumed eigenvector bases do not exist and the theorem does not apply.","tokens_in":25224,"feed_emoji":"🧮","tokens_out":12325,"duration_ms":110997,"temperature":0.7,"pith_summary":"For nonsymmetric and indefinite linear systems, the paper answers a sharp design question: given a fixed fine-space preconditioner $M$ and a coarse-space dimension $n_c$, which restriction $R$ and interpolation $P$ give the best two-level method? The answer is that $P$ and $R$ should be built from the $n_c$ right and left generalized eigenvectors of the matrix pencil $(A,M)$ whose eigenvalues $\\lambda$ have the largest values of $|1-\\lambda|$. In a carefully chosen norm, these transfer operators minimize the error-propagation norm over all possible transfer operators, and the minimum is exactly $|1-\\lambda_{n_c+1}|^{\\nu_1+\\nu_2}$, where $\\nu_1+\\nu_2$ is the number of smoothing steps. This gives a necessary and sufficient test for whether any convergent two-level method exists at a given coarsening. The paper also shows that when $A$ and $M$ are real, optimal real-valued transfer operators exist with the same convergence guarantees.","feed_headline":"Provably optimal transfer operators for nonsymmetric two-level solvers","feed_subtitle":"Given a fixed smoother, the best possible convergence factor is set by the next critical generalized eigenvalue.","key_machinery":"The central object is the generalized eigen-decomposition of the matrix pencil $(A,M)$, with right and left eigenvectors $V_r,V_l$ satisfying $V_l^*AV_r=D_a$ and $V_l^*MV_r=D_m$. The analysis runs in the $N$-norm with $N=V_r^{-*}D^*DV_r^{-1}$, where $D$ is any diagonal, full-rank, CF-split scaling; in this norm the coarse-space projection becomes the block-diagonal operator $\\mathrm{diag}(I,0)$ in the eigenvector basis, so the error propagator has an explicit eigenvalue decomposition and the diagonal $D$ commutes with the smoothing factors. The optimality proof applies the generalized Courant-Fischer-Weyl min-max principle to the diagonal pencil formed from the values $|1-\\lambda_j|$, which yields the lower bound $|1-\\lambda_{n_c+1}|^{\\nu_1+\\nu_2}$. For real $A$ and $M$, a block-diagonal similarity $T$ maps conjugate complex eigenvector pairs to real columns $W_l,W_r$ while preserving the orthogonality relations, which is what allows real-valued transfer operators to inherit the same theory.","core_discovery":"The paper proves that, for the norm induced by $N=V_r^{-*}D^*DV_r^{-1}$, the transfer operators $P_\\sharp$ and $R_\\sharp$---whose ranges are the $n_c$ right and left generalized eigenvectors of $(A,M)$ selected by the $n_c$ largest values of $|1-\\lambda|$---minimize the two-level error-propagation norm over all possible transfer operators. The minimum value is $|1-\\lambda_{n_c+1}|^{\\nu_1+\\nu_2}$ when $n_c