PaperlayerView exact revision on arXiv

Source-linked AI summary

A novel parallel approach for solving some free boundary value problems

Peeyush Singh, Amboru Yalmanda

arXiv:2609.03214v1math.NAcs.NA

TL;DR

Obstacle and free-boundary problems involve solving an equation together with an unknown boundary, and the use of SPIKE banded solvers for constraint optimization remains unexplored. The paper develops parallel direct and iterative formulations; it reports asymptotic linear convergence to machine tolerance in low iteration cycles for its preconditioned second-order solver.

  • Problem

    SPIKE banded solvers have not been extensively investigated for constraint minimization problems such as obstacle problems.

    Source: §1 · p. 3

  • Method

    The paper reformulates the complementarity problem into equivalent functionals and uses a block-decoupled parallel approach with a SPIKE-based direct solver.

    Source: §3 · p. 6, §3.0.1 · p. 8

  • Results

    The preconditioned second-order solver is reported to achieve robust asymptotic linear convergence to machine tolerance within low iteration cycles while maintaining zero network deadlock configurations.

    Source: §6 · p. 32

  • Takeaways & Limitations

    The conclusion presents the line-splitting projection solver as a stable, scalable framework for constrained multidimensional boundary-value operators.

    Source: §6 · p. 33

    The smooth-functional analysis assumes bounded-below functionals with Lipschitz-continuous gradients, including the stated smoothness conditions on F1 and F2.

    Source: §4.1 · pp. 10–11

Abstract

from arXiv · show

This paper introduces a novel, efficient class of parallel direct and indirect iterative schemes to solve general obstacle and free boundary value problems. The uniqueness of the solution for the direct parallel method is established under the assumption that the model problem yields an $M$-matrix. The convergence analysis of the indirect approach is predicated on minimizing the discrete energy functional at each iterative stage of the linear approximation process. Under the aforementioned setting, we establish theoretical convergence results for both smooth and nonsmooth energy functionals defined over a convex set, in the sense of Ferris and Mangasarian \cite{ferris1994parallel}. For the numerical computation of the one-dimensional obstacle problem, we adopt a direct generalized parallel approach based on the SPIKE algorithm \cite{polizzi2006parallel}. To accelerate convergence and reduce computational complexity, a fast recursive version of the scheme is generalized to the nonsmooth case. For two- and three-dimensional obstacle problems, we employ a directional splitting method that treats each directional subproblem as a one-dimensional obstacle minimization problem. By framing the energy functional minimization as a parabolic time-dependent problem and utilizing an Armijo time-stepping rule during the solution update process, we successfully obtain results for higher-dimensional obstacles. Additionally, this study explores the possibility of extending the algorithm into a constrained quadratic programming optimization solver. We also evaluate the framework on image deblurring phenomena under the aforementioned setting, successfully recovering the original images. Finally, numerical illustrations are provided to validate the theoretical results.

1 Introduction

The introduction frames obstacle and free-boundary problems as coupled equation-and-interface problems, then motivates parallel methods by an unexamined opportunity to apply SPIKE solvers to constrained optimization. It also states the classical obstacle model and positions the paper’s parallel algorithm within that setting.

1 Introduction

  • Free-boundary problems require solving both a partial differential equation and its unknown domain boundary, with applications in phase transitions, tribology, finance, and game theory.Examples include melting ice, cavitation between moving contacts, American-style option pricing, and Nash equilibrium.Source: §1 · pp. 1–2
  • SPIKE banded solvers have not yet been explored for constraint optimization, motivating their study for obstacle problems.The introduction describes the work as extending a solver approach associated with Sameh and coworkers.Source: §1 · p. 3

1.1 The classical obstacle model

  • The obstacle model seeks an admissible function that respects the boundary profile and stays above the obstacle while minimizing an energy functional.After discretization, the problem becomes a constrained quadratic program formulated through discrete KKT conditions.Source: §1.1 · pp. 3–4
  • The paper considers parallel algorithms for obstacle and free-boundary problems, with later sections covering their mathematical justification, convergence analysis, and numerical applications.The introduction identifies direct and indirect projected parallel algorithms as part of the study.Source: §1.1 · p. 4

2 Mathematical distributive description

The section formulates convex minimization over a closed convex set in a space decomposed into subspaces. It then expresses the problem through component sets whose minimizations can be carried out sequentially or in parallel.

2 Mathematical distributive description

  • The optimization problem is posed for a convex functional on a reflexive Banach space, with the feasible set closed and convex.The space is decomposed as a direct sum of subspaces.Source: §2 · p. 4
  • The feasible set is decomposed into component sets K_i contained in subspaces V_i.Each vector in V has a unique representation by components in the subspaces.Source: §2 · pp. 4–5
  • The full minimization is reformulated as minimizations over the component sets, solved sequentially or in parallel.The section presents this as an equivalent reformulation of the original problem.Source: §2 · p. 5

3 The projected parallel algorithm

The section develops projected parallel formulations for complementarity systems by partitioning the problem into blocks and decoupling component problems. It presents direct SPIKE-based and iterative approaches, with a uniqueness result for the direct method under an M-matrix assumption.

3 The projected parallel algorithm

  • With invertible diagonal blocks, the partitioned complementarity systems decouple except for top and bottom interface blocks, enabling independent concurrent solves.The proposed equivalent functionals share the same minimizers as the original functional.Source: §3 · p. 6
  • For a nonsingular monotone matrix with nonpositive off-diagonal entries, the transformed system is equivalent to a complementarity system.The monotonicity property is used to preserve inequalities under the decomposition.Source: §3 · pp. 6–7

3.0.1 Direct projection type iterative parallel approach

  • The direct approach uses SPIKE preprocessing and postprocessing to form a reduced complementarity system from interface rows, then recovers the full solution by projection.The reduced problem is treated with LU or UL decomposition and a projection step; the remaining components are then decoupled.Source: §3.0.1 · p. 8
  • Under the assumption that A is an M-matrix, the partitioned complementarity system has a unique solution.The proof reduces uniqueness to the reduced LCP, then uses LU decomposition and projection onto the convex set.Source: §3.0.1 · p. 8
  • The reduced complementarity system retains a banded structure, which the paper identifies as suitable for a recursive algorithm variant.The recursive procedure is introduced after the banded-structure observation.Source: §3.0.1 · p. 8

3.0.2 Iterative Parallel Appraoch

  • The section presents two iterative algorithm types using space decompositions, with parameter selection and convexity invoked in the update discussion.The supplied descriptions identify Type I and Type II but do not fully specify their update rules.Source: §3.0.2 · pp. 9–10

4 General convergence theory for distributive implementation

The section establishes convergence guarantees for a distributed minimization framework, first for smooth objectives and then for the nonsmooth obstacle problem. The guarantees depend on assumptions about the objective, decomposition, and iterates.

4 General convergence theory for distributive implementation

  • The framework treats minimization over a decomposed space through component functionals and corresponding restriction and embedding operators.The section introduces the unconstrained optimization formulation and assumes a decomposition into component subspaces.Source: §4 · p. 10, §4.1 · p. 11

4.1 Parallel distributive analysis for general elliptic problem : smooth optimization

  • With strongly convex component functionals and Lipschitz-continuous gradients, Algorithm 1 converges linearly to the unique minimizer.The functionals must also be bounded from below.Source: §4.1 · p. 12
  • When local minimization is inexact but satisfies the stated descent conditions, every limit point is stationary; strong convexity additionally gives convergence to the unique minimizer.The motivation is that exact local minimization may be computationally infeasible.Source: §4.1 · p. 14
  • For the synchronization update, the iterates converge to the unique minimizer under either of the stated bounds on the combined positive step sizes.The bounds are γ1 + γ2 ≤ 1 or γ1 + γ2 < 2.Source: §4.1 · p. 14

4.2 Parallel distributive analysis for obstacle problem : nonsmooth optimization

  • For the obstacle problem, a stationary point of the minimum-principle optimality function solves the associated linear complementarity minimization problem.The nonsmooth analysis applies the distributed framework to the obstacle problem and characterizes stationarity through an optimality function.Source: §4.2 · pp. 14–15, §4.1 · p. 14
  • For the obstacle algorithm, a bounded sequence of update directions yields convergence to a stationary point or stationary accumulation points.The stationarity guarantee applies when the component functionals are strongly convex with lower-bounded, Lipschitz-continuous gradients and the subspaces are convex.Source: §4.2 · p. 16

5 Numerical Experiment

The experiments apply projected SPIKE and directional splitting to obstacle problems from one to three dimensions, then test the framework on image deblurring. Reported results include a force-driven change in contact topology, a 3D elasticity contact footprint, and a reduced image-deblurring residual.

5.1 Numerical example of obstacle problem Rn, n = 1, 2, 3

  • The one-dimensional tests use direct projected SPIKE and report an exact solution for the obstacle problem.The analytical-validation setup uses zero boundary conditions and zero external force on Ω = (−1, 1).Source: §5 · p. 16, §5.1 · p. 18

5 Numerical Experiment

  • For two- and three-dimensional obstacle problems, directional splitting treats each directional subproblem as a 1D obstacle problem, with 1D SPIKE acting as a preconditioner.The projected-gradient framework uses Armijo backtracking to select steps based on sufficient decrease in the energy functional.Source: §5 · p. 16

5.1 Numerical example of obstacle problem Rn, n = 1, 2, 3

  • For a sharp, non-differentiable pyramid obstacle, the projection loop uses ε = 10^-4 to smooth discontinuous subgradients into a localized boundary layer.The smoothing is introduced to alleviate grid locking along sharp derivative ridges.Source: §5.1 · p. 18
  • As downward force increases, the 2D contact set transitions from an annular ring to a solid disk, avoiding grid-locking and cell-distortion failure modes.The three load scales are λ = 2.0, 7.0, and 35.0.Source: §5.1 · p. 19, Figure 3 · p. 20
  • In the 3D elasticity example, the block deforms against the spherical obstacle, and the figure maps the active contact footprint.The example uses a downward body force with λ = 15.0.Source: §5.1 · p. 21, Figure 4 · p. 22

5.2 Application of parallel algorithm image deblurring problem

  • The reported result shows the system residual norm decreasing from 85.29 to 42.78, with continuous spatial phase characteristics preserved across all subdomain rank boundaries.To address immediate numerical instabilities under simultaneous Jacobi-style block updates, a low-step under-relaxation scaling modifier (ω = 0.05) is enforced.Source: §5.2 · pp. 31–32

6 Conclusion

The paper proposes parallel algorithms for obstacle problems and constrained quadratic programming, and reports a distributed line-splitting SPIKE framework tested on 1D–3D obstacle problems and 2D image deblurring. The authors conclude that the solver exhibits convergence stability, numerical fidelity, and cross-domain versatility.

6 Conclusion

  • The solver is tested on bounded 1D, 2D, and 3D elliptic obstacle problems and a nondiagonally dominant 2D image-deblurring problem.The conclusion describes the framework as driven by distributed line-splitting SPIKE block relaxation.Source: §6 · p. 32
  • The conclusion characterizes the solver as having convergence stability, numerical fidelity, and cross-domain versatility.It describes the stabilized line-splitting projection solver as mathematically rigorous and scalable for constrained multidimensional boundary-value operators.Source: §6 · p. 33
Loading 2609.03214v1…