An official website of the United States government
Sparse matrix dense matrix multiplication (SpMM) is commonly used in applications ranging from scientific computing to graph neural networks. Typically, when SpMM is executed in a distributed platform, communication costs dominate. Such costs depend on how communication is scheduled. If it is scheduled in a sparsity-unaware manner, such as with collectives, execution is often inefficient due to unnecessary data transfers. On the other hand, if communication is scheduled in a fine-grained sparsity-aware manner, communicating only the necessary data, execution can also be inefficient due to high software overhead. We observe that individual sparse matrices often contain regions that are denser and regions that are sparser. Based on this observation, we develop a model that partitions communication into sparsity-unaware and sparsity-aware components. Leveraging the partition, we develop a new algorithm that performs collective communication for the denser regions, and fine-grained, one-sided communication for the sparser regions. We call the algorithm Two-Face. We show that Two-Face attains an average speedup of 2.11x over prior work when evaluated on a 4096-core supercomputer. Additionally, Two-Face scales well with the machine size.
more »
« less
Sum-of-Squares Optimization and the Sparsity Structure of Equiangular Tight Frames
Equiangular tight frames (ETFs) may be used to construct examples of feasible points for semidefinite programs arising in sum-of-squares (SOS) optimization. We show how generalizing the calculations in a recent work of the authors’ that explored this connection also yields new bounds on the sparsity of (both real and complex) ETFs. One corollary shows that Steiner ETFs corresponding to finite projective planes are optimally sparse in the sense of achieving tightness in a matrix inequality controlling overlaps between sparsity patterns of distinct rows of the synthesis matrix. We also formulate several natural open problems concerning further generalizations of our technique.
more »
« less
- Award ID(s):
- 1712730
- PAR ID:
- 10260008
- Date Published:
- Journal Name:
- 2019 13th International conference on Sampling Theory and Applications (SampTA)
- Page Range / eLocation ID:
- 1 to 4
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Empirical applications of the Markov chain model and its spatial extensions suffer from issues induced by the sparse transition probability matrix, which usually results from adopting maximum likelihood estimators (MLEs). Two discrete kernel estimators with cross‐validated parameters are proposed for reducing the sparsity in the estimated transition probability matrix. Monte Carlo experiments suggest that these estimators are not only quite effective in producing a much less sparse matrix, alleviating issues related to sparsity, but also superior to MLEs in terms of lowering the mean squared error for individual and total transition probability, giving rise to the better recovery of the underlying dynamics.more » « less
-
ABSTRACT Empirical transfer functions (ETFs) between seismic records observed at the surface and depth represent a powerful tool to estimate site effects for earthquake hazard analysis. However, conventional modeling of site amplification, with assumptions of horizontally polarized shear waves propagating vertically through 1D layered homogeneous media, often poorly predicts the ETFs, particularly, in which large lateral variations of velocity are present. Here, we test whether more accurate site effects can be obtained from theoretical transfer functions (TTFs) extracted from physics-based simulations that naturally incorporate the complex material properties. We select two well-documented downhole sites (the KiK-net site TKCH05 in Japan and the Garner Valley site, Garner Valley Downhole Array, in southern California) for our study. The 3D subsurface geometry at the two sites is estimated by means of the surface topography near the sites and information from the shear-wave profiles obtained from borehole logs. By comparing the TTFs to ETFs at the selected sites, we show how simulations using the calibrated 3D models can significantly improve site amplification estimates as compared to 1D model predictions. The primary reason for this improvement in 3D models is redirection of scattering from vertically propagating to more realistic obliquely propagating waves, which alleviates artificial amplification at nodes in the vertical-incidence response of corresponding 1D approximations, resulting in improvement of site effect estimation. The results demonstrate the importance of reliable calibration of subsurface structure and material properties in site response studies.more » « less
-
Algebraic Multigrid (AMG) is an extremely popular linear system solver and/or preconditioner approach for matrices obtained from the discretization of elliptic operators. However, its performance and scalability for large systems obtained from unstructured discretizations seem less consistent than for geometric multigrid (GMG). To a large extent, this is due to loss of sparsity at the coarser grids and the resulting increased cost and poor scalability of the matrix-vector multiplication. While there have been attempts to address this concern by designing sparsification algorithms, these affect the overall convergence. In this work, we focus on designing a specialized matrix-vector multiplication (matvec) that achieves high performance and scalability for a large variation in the levels of sparsity. We evaluate distributed and shared memory implementations of our matvec operator and demonstrate the improvements to its scalability and performance in AMG hierarchy and finally, we compare it with PETSc.more » « less
-
Flavin-based electron bifurcation allows enzymes to redistribute energy among electrons by coupling endergonic and exergonic electron transfer reactions. Diverse bifurcating enzymes employ a two-flavin electron transfer flavoprotein (ETF) that accepts hydride from NADH at a flavin (the so-called bifurcating FAD, Bf-FAD). The Bf-FAD passes one electron exergonically to a second flavin thereby assuming a reactive semiquinone state able to reduce ferredoxin or flavodoxin semiquinone. The flavin that accepts one electron and passes it on via exergonic electron transfer is known as the electron transfer FAD (ET-FAD) and is believed to correspond to the single FAD present in canonical ETFs, in domain II. The Bf-FAD is believed to be the one that is unique to bifurcating ETFs, bound between domains I and III. This very reasonable model has yet to be challenged experimentally. Herein we used site-directed mutagenesis to disrupt FAD binding to the presumed Bf site between domains I and III, in the Bf-ETF from Rhodopseudomonas palustris ( Rpa ETF). The resulting protein contained only 0.80 ± 0.05 FAD, plus 1.21 ± 0.04 bound AMP as in canonical ETFs. The flavin was not subject to reduction by NADH, confirming absence of Bf-FAD. The retained FAD displayed visible circular dichroism (CD) similar to that of the ET-FAD of Rpa ETF. Likewise, the mutant underwent two sequential one-electron reductions forming and then consuming anionic semiquinone, reproducing the reactivity of the ET-FAD. These data confirm that the retained FAD in domain II corresponds the ET-FAD. Quantum chemical calculations of the absorbance and CD spectra of each of WT Rpa ETF's two flavins reproduced the observed differences between their CD and absorbance signatures. The calculations for the flavin bound in domain II agreed better with the spectra of the ET-flavin, and those calculated based on the flavin between domains I and III agreed better with spectra of the Bf-flavin. Thus calculations independently confirm the locations of each flavin. We conclude that the site in domain II harbours the ET-FAD whereas the mutated site between domains I and III is the Bf-FAD site, confirming the accepted model by two different tests.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/SampTA45681.2019.9030987
