PaperlayerView exact revision on arXiv

Source-linked AI summary

Condition number analysis and preconditioning of the finite cell method

F. de Prenter, C. V. Verhoosel, G. J. van Zwieten, E. H. van Brummelen

arXiv:1601.05129v2math.NA

TL;DR

Small volume fractions in immersed finite cell discretizations create severe conditioning problems, driven by small basis functions and quasi-linear dependence. The paper derives condition-number scaling relations and develops SIPIC, which combines scaling with local orthonormalization. SIPIC improves finite cell conditioning and iterative-solver behavior without changing the weak formulation or approximation space, while its demonstrated scope is restricted to SPD systems and related assumptions.

  • Problem

    Small cell volume fractions cause ill-conditioning in (I)FCM systems, motivating analysis and preconditioning that avoid altering the weak formulation or approximation space.

  • Method

    SIPIC combines diagonal basis-function scaling with local orthonormalization of quasi-linearly dependent basis functions, using only system-matrix information.

  • Results

    SIPIC effectively improves finite cell condition numbers and iterative-solver performance while preserving the weak formulation and approximation space.

  • Takeaways & Limitations

    Preconditioning enables robust finite cell solutions and detailed mesh-convergence studies without manipulating the weak formulation or approximation space.

  • Takeaways & Limitations

    The study is restricted to symmetric positive definite systems and does not cover convection-dominated flows, Navier–Stokes flows, or incompressible elasticity.

Abstract

from arXiv · show

The (Isogeometric) Finite Cell Method - in which a domain is immersed in a structured background mesh - suffers from conditioning problems when cells with small volume fractions occur. In this contribution, we establish a rigorous scaling relation between the condition number of (I)FCM system matrices and the smallest cell volume fraction. Ill-conditioning stems either from basis functions being small on cells with small volume fractions, or from basis functions being nearly linearly dependent on such cells. Based on these two sources of ill-conditioning, an algebraic preconditioning technique is developed, which is referred to as Symmetric Incomplete Permuted Inverse Cholesky (SIPIC). A detailed numerical investigation of the effectivity of the SIPIC preconditioner in improving (I)FCM condition numbers and in improving the convergence speed and accuracy of iterative solvers is presented for the Poisson problem and for two- and three-dimensional problems in linear elasticity, in which Nitche's method is applied in either the normal or tangential direction. The accuracy of the preconditioned iterative solver enables mesh convergence studies of the finite cell method.

1 Introduction

The Finite Cell Method enables unfitted discretizations for complex and changing geometries, but small physical-domain intersections can severely impair conditioning. This work analyzes the problem and introduces SIPIC, an algebraic preconditioner designed to improve conditioning without changing the weak formulation or approximation space.

  • FCM combines IGA with immersed structured meshes, supporting trimmed, coupled, overlapping, porous, composite, scanned, and moving-boundary domains without repeated remeshing.
  • Small physical-domain volume fractions make FCM systems prone to conditioning problems that impede solving the resulting equations.
  • Existing strategies modify the weak formulation or approximation space, which can affect the solution and compromise stability properties.
  • SIPIC extends basis-function scaling into a fully automated algebraic preconditioner constructed exclusively from system-matrix information.
  • The paper derives an explicit condition-number scaling relation, develops SIPIC, and demonstrates preconditioning effects and mesh-convergence analysis numerically.

2 The finite cell method

The finite cell method uses an unfitted background mesh and a weak formulation with Nitsche-type boundary treatment to impose Dirichlet conditions. Local stabilization preserves coercivity while avoiding conditioning drawbacks associated with global stabilization.

  • FCM embeds the physical domain in a geometrically simple mesh, allowing essential boundary conditions to be handled on an unfitted discretization.
  • The weak formulation adds consistent boundary terms and a penalty term so the bilinear form is symmetric, coercive, and associated with a positive-definite system matrix.
  • The finite cell norm is the equivalent norm induced by the coercive bilinear operator on the finite-dimensional approximation space.
  • Local stabilization chooses cellwise parameters βi satisfying βi > Ci, with coercivity established through trace, Cauchy–Schwarz, Young, and Poincaré inequalities.
  • Global stabilization can impose a large penalty across the entire boundary and may negatively affect conditioning or degenerate FCM into a penalty method; local stabilization avoids these deficiencies.
  • The local constants Ci can be computed through a finite-dimensional generalized eigenvalue problem, whose conditioning is addressed separately in Appendix A.

3 Condition number analysis

For SPD FCM matrices, the condition number is governed by extremal energy-to-coefficient-norm quotients and can grow arbitrarily when trimmed cells have tiny volume fractions. Under stated geometric and discretization assumptions, the derived lower bound worsens with approximation order, and numerical results follow the predicted scaling.

  • For SPD matrices, the condition number is the ratio of maximal and minimal eigenvalues, governing conjugate-gradient convergence and residual-based error estimates.
  • FCM can produce arbitrarily large condition numbers because small trimmed cells yield functions with very small finite cell norms while their coefficient vectors remain unaffected by cell volume.
  • The analysis assumes d > 1, local stabilization, piecewise polynomial bases, uniform mesh size h, and shape-regular trimmed cells with controlled boundary measures.
  • The geometric restrictions used to prove the estimate are not required for constructing the proposed preconditioner.
  • The condition number is bounded below by a constant scaling with η^-(2p+1−2/d), making higher-order p-FEM and IGA especially susceptible to conditioning problems.
  • The numerical results for B-splines and Lagrange bases closely follow the predicted condition-number scaling rates, with similar results for equal-order bases.

4 Algebraic preconditioning for FCM

The paper develops SIPIC, an algebraic preconditioner for FCM that targets two distinct sources of small eigenvalues: poorly scaled basis functions and quasi-linear dependence caused by trimming. It constructs a modified basis without changing the weak formulation or approximation space, and numerical results show strong conditioning improvements with limited fill-in.

  • Preconditioner construction: SIPIC constructs an alternative basis algebraically from the original system matrix, preserving the weak formulation, approximation space, solution, and stability properties.The preconditioner is built from scaling and orthonormalization operations applied to the system matrix.
  • Sources of ill-conditioning: Ill-conditioning arises from small eigenvalues caused by basis functions with small FCM norms or by quasi-linear dependence after trimming.The two mechanisms require different remedies: diagonal scaling addresses small norms, while local orthonormalization addresses near dependence.
  • Preconditioner construction: Diagonal scaling improves conditioning for small-norm basis functions but remains insufficient when trimmed basis functions become quasi-linearly dependent.For quasi-linear dependence, the smallest eigenvalue and condition number remain dependent on the volume fraction, although the scaling rate improves over the original system.
  • Preconditioner construction: Local Gram-Schmidt orthonormalization remedies quasi-linear dependence, and the resulting algebraic preconditioner is interpreted as a symmetric incomplete permuted inverse Cholesky factorization.The preconditioner has the form S = D⊥GD and approximates the conjugate permutation of an incomplete inverse Cholesky decomposition.
  • Implementation considerations: The construction algorithm may eliminate basis functions when machine-precision dependence causes zero diagonal entries after orthonormalization, while preserving the approximation space up to machine precision.The stabilization test uses ε = 10^2 · eps in the reported simulations.
  • Numerical behavior: SIPIC drastically improves condition numbers across the tested cases, while cubic B-spline tests show approximately 1.5% or 0.5% relative fill-in for γ = 0.9 or γ = 0.93.Increasing the threshold reduces fill-in without affecting the observed preconditioning effectiveness; the fill-in remains local.

5 Numerical simulations: SIPIC preconditioned finite cell analysis

Numerical tests on two- and three-dimensional elasticity problems show that SIPIC removes the volume-fraction dependence of conditioning, accelerates CG convergence, and enables accurate mesh-convergence studies.

  • 5.1 Plate with a circular hole: The plate-with-hole test uses a 45°-rotated Cartesian background mesh, quadratic B-spline spaces, and ten uniformly refined meshes.The sequence ranges from 4 intersecting elements on the coarsest mesh to 216,672 on the finest.
  • 5.1 Plate with a circular hole: SIPIC makes the preconditioned condition number essentially independent of the smallest cell volume fraction, while the original system follows the predicted scaling relation.This behavior is observed despite varying the mesh size.
  • 5.1 Plate with a circular hole: Without preconditioning, insufficient linear-solver accuracy becomes dominant under mesh refinement, whereas SIPIC improves the strain-energy error and supports mesh convergence.The original system did not converge within 100,000 CG iterations for the finest mesh at the smallest tested tolerance.
  • 5.2 Quarter solid torus: The quarter-solid-torus test has 592,680 degrees of freedom, so condition numbers are impractical to compute and solver performance is evaluated instead.Weak and strong Dirichlet imposition produce similar CG convergence for both original and SIPIC-preconditioned systems.
  • 5.2 Quarter solid torus: SIPIC reduces the CG iterations needed to reach a residual of 10^-7 by more than a factor of 100 and yields optimal asymptotic mesh convergence for both boundary-condition treatments.The observed convergence rates closely resemble the standard finite-element rate h^4.

6 Concluding remarks

The paper establishes how small trimmed-cell volume fractions drive ill-conditioning and introduces SIPIC to address the two identified sources without changing the weak formulation or approximation space.

  • Conditioning analysis: The condition number is inversely proportional to the smallest trimmed-cell volume fraction, with dependence scaling as the power 2p of basis order p.Globally stabilized systems exhibit an even stronger volume-fraction dependence.
  • SIPIC preconditioning: SIPIC combines diagonal scaling for small basis functions with local Gram-Schmidt orthonormalization for quasi-linearly dependent basis functions.The preconditioner is algebraic and uses only information from the finite cell system matrix.
  • Practical advantages: Unlike alternatives that manipulate the weak formulation or approximation space, SIPIC is non-intrusive and constructed at negligible computational cost.The method is straightforward to implement because it is algebraic.
  • Numerical effect: SIPIC effectively improves finite cell conditioning, as observed in condition-number computations and iterative-solver performance.The supplied convergence figure concerns strain energy under mesh refinement for original and SIPIC-preconditioned results.
  • Scope: The study is restricted to finite cell systems and symmetric positive definite systems, excluding convection-dominated flows and mixed problems such as incompressible elasticity.Applying SIPIC elsewhere also requires selecting an appropriate orthonormalization threshold.

Appendix A Local eigenvalue problem conditioning

The local eigenvalue problem can become numerically difficult because its gradient-based matrix is singular and may remain poorly conditioned after kernel removal on small-volume cells.

  • Sources of difficulty: The local matrix Vi is singular because it is based solely on gradients of the shape functions, although ker(Vi) ⊂ ker(Bi) prevents this from being fundamentally problematic for computing Ci.The kernel can nevertheless reduce the robustness of largest-eigenvalue computations.
  • Sources of difficulty: After removing ker(Vi), poor conditioning can persist on small-volume cells because basis functions may be quasi-linearly dependent.This is a second local numerical difficulty beyond the matrix kernel.
  • Remedy: A local change of basis using monomials circumvents these eigenvalue-computation difficulties because the eigenvalue problem is local to each cell.With this basis, diagonal scaling is sufficient for robust computation of Ci.
  • Remedy: Centering monomials at the trimmed cell’s center of mass reduces quasi-linear dependence by separating higher-order terms after diagonal scaling.The construction also simplifies the kernel structure of Vi.

Appendix B Upper bounds for F2(·, ·) and F3(·, ·)

The appendix derives upper bounds for the terms governing finite cell system conditioning and explains why globally stabilized systems have a different condition-number slope.

  • Upper-bound assumptions: The bounds on F2(·, ·) and F3(·, ·) are derived under the stated assumptions, with an additional polynomial-basis bound involving CV independent of mesh size h.The polynomial-basis assumption is that CV is approximately 1 and mesh-size independent.
  • Support-count bounds: For piecewise polynomial spaces, at most (p + 1)^d functions are supported on a cell, while a function is supported on at most (p + 1)^d B-spline cells or 2^d cells for most other bases.These support-count bounds control the sum of terms per function.
  • Matrix bounds: The support-count estimates bound the sum of terms per function by CF23hd−2 and consequently bound the matrix’s infinity and 1-norms through symmetry.The norm bounds follow from the corresponding term estimates.
  • Global stabilization: With global stabilization, the bound for βi depends on η rather than ηi, producing a different estimate for the globally stabilized condition number.The appendix states that this explains the different slope observed under global stabilization.
  • Global stabilization: The displayed globally stabilized condition-number estimate differs from the locally stabilized relation and accounts for the slope change observed in Sections 3.3 and 4.4.The estimate is presented as the appendix’s resulting condition-number bound.

Appendix C Machine precision instabilities in the SIPIC construction algorithm

The SIPIC construction can become unstable near machine precision when nearly dependent matrix rows make Gram-Schmidt renormalization divide by zero.

  • Illustrative example: The appendix illustrates the machine-precision problem with a 2 × 2 matrix whose condition number is κ2 = 2/ε2 − 1 for ε ≪ 1.The example uses a parameter ε that makes the matrix highly ill-conditioned.
  • Instability mechanism: When ε2 ∼ eps, the matrix rows become linearly dependent up to machine precision, impeding SIPIC construction.The failure occurs during the renormalization step following Gram-Schmidt orthonormalization.
  • Instability mechanism: For this case, Gram-Schmidt produces an orthogonalized matrix before normalization, but normalization requires division by the square root of a quantity that becomes numerically problematic.The stated construction uses A⊥ = GAGT with D = diag(A) = I.
Loading 1601.05129v2…