Search

This paper proposes an efficient general alternating-direction implicit (GADI) framework for solving large sparse linear systems. The convergence property of the GADI framework is discussed. Most of the existing ADI methods can be viewed as particular schemes of the developed framework. Meanwhile the GADI framework can derive new ADI methods. Moreover, as the algorithm efficiency is sensitive to the splitting parameters, we offer a data-driven approach, the Gaussian process regression (GPR) method based on the Bayesian inference, to predict the GADI framework's relatively optimal parameters. The GPR method requires a small training data set to learn the regression prediction mapping, which has sufficient accuracy and high generalization capability. It allows us to efficiently solve linear systems with a one-shot computation, and does not require any repeated computations to obtain relatively optimal splitting parameters. Finally, we use the three-dimensional convection-diffusion equation and continuous Sylvester matrix equation to examine the performance of our proposed methods. Numerical results demonstrate that the proposed framework is faster tens to thousands of times than the existing ADI methods, such as (inexact) Hermitian and skew-Hermitian splitting type methods in which the consumption of obtaining relatively optimal splitting parameters is ignored. Due to the efficiency of the developed methods, we can solve much larger linear systems which these existing ADI methods have been not reached.

A vertebrate interval graph is an interval graph in which the maximum size of a set of independent vertices equals the number of maximal cliques. For any fixed $v \ge 1$, there is a polynomial-time algorithm for deciding whether a vertebrate interval graph admits a vertex partition into two induced subgraphs with claw number at most $v$. In particular, when $v = 2$, whether a vertebrate interval graph can be partitioned into two proper interval graphs can be decided in polynomial time., Comment: Sequel to arXiv:2109.11498

The claw number of a graph $G$ is the largest number $v$ such that $K_{1,v}$ is an induced subgraph of $G$. Interval graphs with claw number at most $v$ are cluster graphs when $v = 1$, and are proper interval graphs when $v = 2$. Let $\kappa(n,v)$ be the smallest number $k$ such that every interval graph with $n$ vertices admits a vertex partition into $k$ induced subgraphs with claw number at most $v$. Let $\check\kappa(w,v)$ be the smallest number $k$ such that every interval graph with claw number $w$ admits a vertex partition into $k$ induced subgraphs with claw number at most $v$. We show that $\kappa(n,v) = \lfloor\log_{v+1} (n v + 1)\rfloor$, and that $\lfloor\log_{v+1} w\rfloor + 1 \le \check\kappa(w,v) \le \lfloor\log_{v+1} w\rfloor + 3$. Besides the combinatorial bounds, we also present a simple approximation algorithm for partitioning an interval graph into the minimum number of induced subgraphs with claw number at most $v$, with approximation ratio $3$ when $1 \le v \le 2$, and $2$ when $v \ge 3$.

Let $p(m)$ (respectively, $q(m)$) be the maximum number $k$ such that any tree with $m$ edges can be transformed by contracting edges (respectively, by removing vertices) into a caterpillar with $k$ edges. We derive closed-form expressions for $p(m)$ and $q(m)$ for all $m \ge 1$. The two functions $p(n)$ and $q(n)$ can also be interpreted in terms of alternating paths among $n$ disjoint line segments in the plane, whose $2n$ endpoints are in convex position.

We construct a family of 17 disjoint axis-parallel line segments in the plane that do not admit a circumscribing polygon.

Deciding whether a family of disjoint axis-parallel line segments in the plane can be linked into a simple polygon (or a simple polygonal chain) by adding segments between their endpoints is NP-hard., Comment: Strengthens the results in arXiv:2108.12812

We study several problems on geometric packing and covering with movement. Given a family $\mathcal{I}$ of $n$ intervals of $\kappa$ distinct lengths, and another interval $B$, can we pack the intervals in $\mathcal{I}$ inside $B$ (respectively, cover $B$ by the intervals in $\mathcal{I}$) by moving $\tau$ intervals and keeping the other $\sigma = n - \tau$ intervals unmoved? We show that both packing and covering are W[1]-hard with any one of $\kappa$, $\tau$, and $\sigma$ as single parameter, but are FPT with combined parameters $\kappa$ and $\tau$. We also obtain improved polynomial-time algorithms for packing and covering, including an $O(n\log^2 n)$ time algorithm for covering, when all intervals in $\mathcal{I}$ have the same length.

Deciding whether a family of disjoint line segments in the plane can be linked into a simple polygon (or a simple polygonal chain) by adding segments between their endpoints is NP-hard., Comment: Added a postscript and two more references

We present improved universal covers for carpenter's rule folding in the plane.

In this paper, we develop an adaptive high-order surface finite element method (FEM) incorporating the spectral deferred correction method for chain contour discretization to solve polymeric self-consistent field equations on general curved surfaces. The high-order surface FEM is obtained by the high-order surface geometrical approximation and the high-order function space approximation. Numerical results demonstrate that the precision order of these methods is consistent with the theoretical prediction. In order to describe the sharp interface in the strongly segregated system more accurately, an adaptive FEM equipped with a new Log marking strategy is proposed. Compared with the traditional strategy, the Log marking strategy can not only label the elements that need to be refined or coarsened, but also give the refined or coarsened times, which can make full use of the information of a posterior error estimator and improve the ecciency of the adaptive algorithm. To demonstrate the power of our approach, we investigate the self-assembled patterns of diblock copolymers on several distinct curved surfaces. Numerical results illustrate the ecciency of the proposed method, especially for strongly segregated systems with economical discretization nodes., Comment: 23 pages, 14 figures

Great achievements in last five years, such as record-efficient amorphous/crystalline silicon heterojunction (SHJ) solar cells and cutting-edge perovskite/SHJ tandem solar cells, place hydrogenated amorphous silicon (a-Si:H) at the forefront of emerging photovoltaics. Due to the extremely low doping efficiency of trivalent boron (B) in amorphous tetravalent silicon, light harvesting of aforementioned devices are limited by their fill factors (FF), which is a direct metric of the charge carrier transport. It is challenging but crucial to develop highly conductive doped a-Si:H for minimizing the FF losses. Here we report intensive light soaking can efficiently boost the dark conductance of B-doped a-Si:H "thin" films, which is an abnormal Staebler-Wronski effect. By implementing this abnormal effect to SHJ solar cells, we achieve a certificated power conversion efficiency (PCE) of 25.18% (26.05% on designated area) with FF of 85.42% on a 244.63-cm2 wafer. This PCE is one of the highest reported values for total-area "top/rear" contact silicon solar cells. The FF reaches 98.30 per cent of its Shockley-Queisser limit., Comment: 34 pages, 4 figures in main context,11 figures in supplementary materials