Skip to main content
eScholarship
Open Access Publications from the University of California

Scholarly Works (23 results)

  • Article
Lawrence Berkeley National Laboratory (2001)

A framework for constructing circulant and block circulant preconditioners ($C$) for a symmetric linear system $Ax=b$ arising from certain signal and image processing applications is presented in this paper. The proposed scheme does not make explicit use of matrix elements of $A$. It is ideal for applications in which $A$ only exists in the form of a matrix vector multiplication routine, and in which the process of extracting matrix elements of $A$ is costly. The proposed algorithm takes advantage of the fact that for many linear systems arising from signal or image processing applications, eigenvectors of $A$ can be well represented by a small number of Fourier modes. Therefore, the construction of $C$ can be carried out in the frequency domain by carefully choosing its eigenvalues so that the condition number of $C^TAC$ can be reduced significantly. We illustrate how to construct the spectrum of $C$ in a way such that the smallest eigenvalues of $C^TAC$ overlaps with those of $A$ extremely well while the largest eigenvalues of $C^TAC$ are smaller than those of $A$ by several orders of magnitude. Numerical examples are provided to demonstrate the effectiveness of the preconditioner on accelerating the solution of linear systems arising from image reconstruction application.

    Cover page: Matrix-free constructions of circulant and block circulant preconditioners
    • Article
    LBL Publications (2008)
      Cover page: Using Perturbed QR Factorizations To Solve Linear Least-Squares Problems
      • Article
      LBL Publications (2003)
        Cover page: Nested dissection orderings for LU factorization with static pivoting
        • Article
        • Peer Reviewed
        UC Berkeley Previously Published Works (2016)
        Systems of linear equations arise at the heart of many scientific and engineering applications. Many of these linear systems are sparse; i.e., most of the elements in the coefficient matrix are zero. Direct methods based on matrix factorizations are sometimes needed to ensure accurate solutions. For example, accurate solution of sparse linear systems is needed in shift-invert Lanczos to compute interior eigenvalues. The performance and resource usage of sparse matrix factorizations are critical to time-to-solution and maximum problem size solvable on a given platform. In many applications, the coefficient matrices are symmetric, and exploiting symmetry will reduce both the amount of work and storage cost required for factorization. When the factorization is performed on large-scale distributed memory platforms, communication cost is critical to the performance of the algorithm. At the same time, network topologies have become increasingly complex, so that modern platforms exhibit a high level of performance variability. This makes scheduling of computations an intricate and performance-critical task. In this paper, we investigate the use of an asynchronous task paradigm, one-sided communication and dynamic scheduling in implementing sparse Cholesky factorization (symPACK) on large-scale distributed memory platforms. Our solver symPACK relies on efficient and flexible communication primitives provided by the UPC++ library. Performance evaluation shows good scalability and that symPACK outperforms state-of-the-art parallel distributed memory factorization packages, validating our approach on practical cases.
          Cover page: An Asynchronous Task-based Fan-Both Sparse Cholesky Solver
          • Article
          • Peer Reviewed
          LBL Publications (2023)
          Water flowing under ice sheets and glaciers can have a strong influence on ice dynamics, particularly through pressure changes, suggesting that a comprehensive ice sheet model should include the effect of basal hydrology. Modeling subglacial hydrology remains a challenge, however, mainly due to the range of spatial and temporal scales involved - from subglacial channels to vast subglacial lakes. Additionally, networks of subglacial drainage channels dynamically evolve over time. To address some of these challenges, we have developed an adaptive mesh refinement (AMR) model based on the Chombo software framework. We extend the model proposed by with a small but significant change to accommodate the transition from unresolved to resolved flow features. We handle the strong nonlinearities present in the equations by resorting to an efficient nonlinear full approximation scheme multigrid (FAS-MG) algorithm. We outline the details of the algorithm and present convergence analysis results demonstrating its good performance. Additionally, we present results validating our approach, using test cases from the Subglacial Hydrology Model Intercomparison Project (SHMIP) . We finish by presenting a more complex, 100 km-by-100 km synthetic test case with peaks and valleys that we use to investigate the effective pressure distribution as the number of AMR levels increases. These preliminary results suggest that a minimum spatial resolution is needed to properly capture channel features, but additional work is required to precisely quantify this and its impact on accurately modeling the coupled ice sheet-hydrology system. The efficiency of our approach, relying on localized refinement, is also demonstrated. Future work will include coupling the SUbglacial Hydrology MOdel (SUHMO) with the BISICLES AMR ice sheet model , both built on the same numerical framework.
            Cover page: SUHMO: an adaptive mesh refinement SUbglacial Hydrology MOdel v1.0Creative Commons 'BY' version 4.0 license
            • Article
            • Peer Reviewed
            UC Berkeley Previously Published Works (2016)
              • Article
              Lawrence Berkeley National Laboratory (2005)

              Sparse systems of linear equations and eigen-equations arise at the heart of many large-scale, vital simulations in DOE. Examples include the Accelerator Science and Technology SciDAC (Omega3P code, electromagnetic problem), the Center for Extended Magnetohydrodynamic Modeling SciDAC(NIMROD and M3D-C1 codes, fusion plasma simulation). The Terascale Optimal PDE Simulations (TOPS)is providing high-performance sparse direct solvers, which have had significant impacts on these applications. Over the past several years, we have been working closely with the other SciDAC teams to solve their large, sparse matrix problems arising from discretization of the partial differential equations. Most of these systems are very ill-conditioned, resulting in extremely poor convergenc deployed our direct methods techniques in these applications, which achieved significant scientific results as well as performance gains. These successes were made possible through the SciDAC model of computer scientists and application scientists working together totake full advantage of terascale computing systems and new algorithms research.

                Cover page: The Roles of Sparse Direct Methods in Large-scale Simulations
                • Article
                • Peer Reviewed
                LBL Publications (2023)
                Sparse symmetric positive definite systems of equations are ubiquitous in scientific workloads and applications. Parallel sparse Cholesky factorization is the method of choice for solving such linear systems. Therefore, the development of parallel sparse Cholesky codes that can efficiently run on today's large-scale heterogeneous distributed-memory platforms is of vital importance. Modern supercomputers offer nodes that contain a mix of CPUs and GPUs. To fully utilize the computing power of these nodes, scientific codes must be adapted to offload expensive computations to GPUs. We present symPACK, a GPU-capable parallel sparse Cholesky solver that uses one-sided communication primitives and remote procedure calls provided by the UPC++ library. We also utilize the UPC++ "memory kinds"feature to enable efficient communication of GPU-resident data. We show that on a number of large problems, symPACK outperforms comparable state-of-the-art GPU-capable Cholesky factorization codes by up to 14x on the NERSC Perlmutter supercomputer.
                  Cover page: symPACK: A GPU-Capable Fan-Out Sparse Cholesky SolverCreative Commons 'BY' version 4.0 license
                  • Article
                  Lawrence Berkeley National Laboratory (2004)

                  Algebraic sub-structuring refers to the process of applying matrix reordering and partitioning algorithms to divide a large sparse matrix into smaller submatrices from which a subset of spectral components are extracted and combined to form approximate solutions to the original problem. In this paper, we show that algebraic sub-structuring can be effectively used to solve generalized eigenvalue problems arising from the finite element analysis of an accelerator structure.

                    Cover page: Algebraic sub-structuring for electromagnetic applications
                    • Article
                    • Peer Reviewed
                    UC Berkeley Previously Published Works (2015)
                    We present a special symmetric Lanczos algorithm and a kernel polynomial method (KPM) for approximating the absorption spectrum of molecules within the linear response time-dependent density functional theory (TDDFT) framework in the product form. In contrast to existing algorithms, the new algorithms are based on reformulating the original non-Hermitian eigenvalue problem as a product eigenvalue problem and the observation that the product eigenvalue problem is self-adjoint with respect to an appropriately chosen inner product. This allows a simple symmetric Lanczos algorithm to be used to compute the desired absorption spectrum. The use of a symmetric Lanczos algorithm only requires half of the memory compared with the nonsymmetric variant of the Lanczos algorithm. The symmetric Lanczos algorithm is also numerically more stable than the nonsymmetric version. The KPM algorithm is also presented as a low-memory alternative to the Lanczos approach, but the algorithm may require more matrix-vector multiplications in practice. We discuss the pros and cons of these methods in terms of their accuracy as well as their computational and storage cost. Applications to a set of small and medium-sized molecules are also presented.
                      Cover page: Efficient Algorithms for Estimating the Absorption Spectrum within Linear Response TDDFT
                      Top