Semiseparable matrices and many other rank-structured have been widely used in developing new fast matrix algorithms. In this paper, we generalize the hierarchically semiseparable (HSS) representations propose some algorithms for HSS matrices. We represent terms of general binary trees use simplified postordering notation forms. Fast including structure generation form Cholesky factorization are developed. Moreover, provide a linear complexity explicit ULV algorithm symmetric positive...

In this paper we develop a fast direct solver for large discretized linear systems using the supernodal multifrontal method together with low-rank approximations. For arising from certain partial differential equations such as elliptic equations, during Gaussian elimination of matrices proper ordering, fill-in has property: all off-diagonal blocks have small numerical ranks definition blocks. Matrices property can be efficiently approximated semiseparable structures called hierarchically...

ABSTRACT We consider the modeling of (polarized) seismic wave propagation on a rectangular domain via discretization and solution inhomogeneous Helmholtz equation in 3D, by exploiting parallel multifrontal sparse direct solver equipped with Hierarchically Semi‐Separable (HSS) structure to reduce computational complexity storage. In particular, we are concerned solving this large domain, for number different forcing terms context problems general, particular. resort parsimonious mixed grid...

We propose a superfast solver for Toeplitz linear systems based on rank structured matrix methods and randomized sampling. The uses displacement equations to transform $T$ into Cauchy-like $\mathcal{C}$, which is known have low-numerical-rank off-diagonal blocks. Thus, we design fast scheme constructing hierarchically semiseparable (HSS) approximation where the HSS generators internal structures. Unlike classical methods, our employs sampling techniques together with matrix-vector...

Rank structures provide an opportunity to develop new efficient numerical methods for practical problems, when the off-diagonal blocks of certain dense intermediate matrices have small (numerical) ranks. In this work, we present a framework structured direct factorizations general sparse matrices, including discretized PDEs on meshes, based multifrontal method and hierarchically semiseparable (HSS) matrices. We prove idea replacing complex operations by fast simple ones performed compact...

We propose randomized direct solvers for large sparse linear systems, which integrate randomization into rank structured multifrontal methods. The use of highly simplifies various essential steps in solutions, where fast operations on skinny matrix-vector products replace traditional complex ones dense or matrices. new methods thus significantly enhance the flexibility and efficiency using solutions. also consider a variety techniques, such as some graph methods, inclusion additional...

We present some superfast ($O((m+n)\log^{2}(m+n))$ complexity) and stable structured direct solvers for $m\times n$ Toeplitz least squares problems. Based on the displacement equation, a matrix $T$ is first transformed into Cauchy-like $\mathcal{C}$, which can be shown to have small off-diagonal numerical ranks when diagonal blocks are rectangular. generalize standard hierarchically semiseparable (HSS) representations rectangular ones, construct HSS approximation $\mathcal{C}$ in nearly...

In this paper we develop a new superfast solver for Toeplitz systems of linear equations. To solve many people use displacement equation methods. With structures, matrices can be transformed into Cauchy-like using the FFT or other trigonometric transformations. These have special property, that is, their off-diagonal blocks small numerical ranks. This low-rank property plays central role in our solver. It enables us to quickly approximate by structured called sequentially semiseparable (SSS)...

We present a massively parallel structured multifrontal solver for the equations describing time-harmonic elastic waves in 3-D anisotropic media. use multicomponent second-order finite-difference method. extend corresponding stencil to enhance accuracy of discretization without increasing order. This is aligned with tolerance level used Hierarchically SemiSeparable (HSS) low rank matrix compression underlying our solver. The interplay between finite and yields key strategy which leads...

The distance to uncontrollability for a linear control system is the (in 2-norm) nearest uncontrollable system. We present an algorithm based on methods of Gu and Burke-Lewis-Overton that estimates any prescribed accuracy. new method requires O(n4 ) operations average, which improvement over previous have complexity O(n6 ), where n order Numerical experiments indicate reliable in practice.

Given a symmetric positive definite matrix A, we compute structured approximate Cholesky factorization $A\approx\mathbf{R}^{T}\mathbf{R}$ up to any desired accuracy, where $\mathbf{R}$ is an upper triangular hierarchically semiseparable (HSS) matrix. The stable, robust, and efficient. method compresses off-diagonal blocks with rank-revealing orthogonal decompositions. In the meantime, semidefinite terms are automatically implicitly added Schur complements in so that approximation...

In recent years, hierarchical structured matrices have been widely used in fast solutions of integral equations, PDEs, matrix (such as Toeplitz) problems, companion eigenproblems, etc. this paper, we systematically study the complexity some algorithms, terms hierarchically semiseparable (HSS) matrices. Several important aspects are considered. We perform detailed analysis for typical HSS with aid certain graph techniques. This helps us provide significant improvements to classical methods....

Hierarchically semiseparable (HSS) matrix techniques are emerging in constructing superfast direct solvers for both dense and sparse linear systems. Here, we develop a set of novel parallel algorithms key HSS operations that used solving large These rank-revealing QR factorization, constructions with hierarchical compression, ULV solutions. The tree-based parallelism is fully exploited at the coarse level. \textttBLACS \textttScaLAPACK libraries to facilitate kernel fine-grained We appply...

We present a superfast divide-and-conquer method for finding all the eigenvalues as well eigenvectors (in structured form) of class symmetric matrices with off-diagonal ranks or numerical bounded by $r$, approximation accuracy due to compression. More specifically, complexity is $O(r^{2}n\log n)+O(rn\log^{2}n)$, where $n$ order matrix. Such are often encountered in practical computations banded matrices, Toeplitz Fourier space), and certain discretized problems. They can be represented...

We present a structured parallel geometry-based multifrontal sparse solver using hierarchically semiseparable (HSS) representations and exploiting the inherent low-rank structures. Parallel strategies for nested dissection ordering (taking low rankness into account), symbolic factorization, numerical factorization are shown. In particular, we demonstrate how to manage two layers of tree parallelism integrate HSS operations within factorization. Such algorithm can be shown have asymptotically...

In this paper, we propose a structured bisection method with adaptive randomized sampling for finding selected or all of the eigenvalues certain real symmetric matrices $A$. For $A$ low-rank property, construct hierarchically semiseparable (HSS) approximation and show how to quickly evaluate update its inertia in method. Unlike some existing HSS constructions, methods here do not require knowledge off-diagonal (numerical) ranks advance. Moreover, weak rank property slowly decaying singular...

For general symmetric positive definite (SPD) matrices, we present a framework for designing effective and robust black-box preconditioners via structured incomplete factorization. In scaling-and-compression strategy, off-diagonal blocks are first scaled on both sides (by the inverses of factors corresponding diagonal blocks) then compressed into low-rank approximations. ULV-type factorizations computed. A resulting prototype preconditioner is always definite. Generalizations to practical...

We design efficient and distributed-memory parallel randomized direct solvers for large structured dense linear systems, including a fully matrix-free version based on matrix-vector multiplications partially one. The coefficient matrix $A$ has an off-diagonal low-rank structure, as often encountered in practical applications such Toeplitz systems discretized integral partial differential equations. A framework solution is shown. Scalable adaptive sampling hierarchical compression algorithms...