The Experts below are selected from a list of 321 Experts worldwide ranked by ideXlab platform
Zhuo Feng - One of the best experts on this subject based on the ideXlab platform.
-
GRASS: Graph Spectral Sparsification Leveraging Scalable Spectral Perturbation Analysis
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020Co-Authors: Zhuo FengAbstract:Spectral graph sparsification aims to find ultra-sparse subgraphs whose Laplacian matrix can well approximate the original Laplacian eigenvalues and eigenvectors. In recent years, Spectral sparsification techniques have been extensively studied for accelerating various numerical and graph-related applications. Prior nearly-linear-time Spectral sparsification methods first extract low-stretch spanning tree from the original graph to form the backbone of the sparsifier, and then recover small portions of Spectrally-critical off-tree edges to the spanning tree to significantly improve the approximation quality. However, it is not clear how many off-tree edges should be recovered for achieving a desired Spectral similarity level within the sparsifier. Motivated by recent graph signal processing techniques, this work proposes a similarity-aware Spectral graph sparsification framework that leverages efficient Spectral off-tree edge embedding and filtering schemes to construct Spectral sparsifiers with guaranteed Spectral similarity (relative condition number) level. An iterative graph densification scheme is also introduced to facilitate efficient and effective filtering of off-tree edges for highly ill-conditioned problems. The proposed method has been validated using various kinds of graphs obtained from public domain sparse matrix collections relevant to very large-scale integration computer-aided design, finite element analysis, as well as social and data networks frequently studied in many machine learning and data mining applications. For instance, a sparse SDD matrix with 40 million unknowns and 180 million nonzeros can be solved (1E-3 accuracy level) within 2 min using a single CPU core and about 6-GB memory.
-
GRASS: Graph Spectral Sparsification Leveraging Scalable Spectral Perturbation Analysis
arXiv: Data Structures and Algorithms, 2019Co-Authors: Zhuo FengAbstract:Spectral graph sparsification aims to find ultra-sparse subgraphs whose Laplacian matrix can well approximate the original Laplacian eigenvalues and eigenvectors. In recent years, Spectral sparsification techniques have been extensively studied for accelerating various numerical and graph-related applications. Prior nearly-linear-time Spectral sparsification methods first extract low-stretch spanning tree from the original graph to form the backbone of the sparsifier, and then recover small portions of Spectrally-critical off-tree edges to the spanning tree to significantly improve the approximation quality. However, it is not clear how many off-tree edges should be recovered for achieving a desired Spectral similarity level within the sparsifier. Motivated by recent graph signal processing techniques, this paper proposes a similarity-aware Spectral graph sparsification framework that leverages efficient Spectral off-tree edge embedding and filtering schemes to construct Spectral sparsifiers with guaranteed Spectral similarity (relative condition number) level. An iterative graph densification scheme is also introduced to facilitate efficient and effective filtering of off-tree edges for highly ill-conditioned problems. The proposed method has been validated using various kinds of graphs obtained from public domain sparse matrix collections relevant to VLSI CAD, finite element analysis, as well as social and data networks frequently studied in many machine learning and data mining applications. For instance, a sparse SDD matrix with 40 million unknowns and 180 million nonzeros can be solved (1E-3 accuracy level) within two minutes using a single CPU core and about 6GB memory.
-
Spectral graph sparsification in nearly linear time leveraging efficient Spectral Perturbation analysis
Design Automation Conference, 2016Co-Authors: Zhuo FengAbstract:Spectral graph sparsification aims to find an ultra-sparse subgraph whose Laplacian matrix can well approximate the original Laplacian matrix in terms of its eigenvalues and eigenvectors. The resultant sparsified subgraph can be efficiently leveraged as a proxy in a variety of numerical computation applications and graph-based algorithms. This paper introduces a practically efficient, nearly-linear time Spectral graph sparsification algorithm that can immediately lead to the development of nearly-linear time symmetric diagonally-dominant (SDD) matrix solvers. Our Spectral graph sparsi-fication algorithm can efficiently build an ultra-sparse subgraph from a spanning tree subgraph by adding a few “Spectrally-critical” off-tree edges back to the spanning tree, which is enabled by a novel Spectral Perturbation approach and allows to approximately preserve key Spectral properties of the original graph Laplacian. Extensive experimental results confirm the nearly-linear runtime scalability of an SDD matrix solver for large-scale, real-world problems, such as VLSI, thermal and finite-element analysis problems, etc. For instance, a sparse SDD matrix with 40 million unknowns and 180 million nonzeros can be solved (1E-3 accuracy level) within two minutes using a single CPU core and about 6GB memory.
-
DAC - Spectral graph sparsification in nearly-linear time leveraging efficient Spectral Perturbation analysis
Proceedings of the 53rd Annual Design Automation Conference, 2016Co-Authors: Zhuo FengAbstract:Spectral graph sparsification aims to find an ultra-sparse subgraph whose Laplacian matrix can well approximate the original Laplacian matrix in terms of its eigenvalues and eigenvectors. The resultant sparsified subgraph can be efficiently leveraged as a proxy in a variety of numerical computation applications and graph-based algorithms. This paper introduces a practically efficient, nearly-linear time Spectral graph sparsification algorithm that can immediately lead to the development of nearly-linear time symmetric diagonally-dominant (SDD) matrix solvers. Our Spectral graph sparsification algorithm can efficiently build an ultra-sparse subgraph from a spanning tree subgraph by adding a few "Spectrally-critical" off-tree edges back to the spanning tree, which is enabled by a novel Spectral Perturbation approach and allows to approximately preserve key Spectral properties of the original graph Laplacian. Extensive experimental results confirm the nearly-linear runtime scalability of an SDD matrix solver for large-scale, real-world problems, such as VLSI, thermal and finite-element analysis problems, etc. For instance, a sparse SDD matrix with 40 million unknowns and 180 million nonzeros can be solved (1E-3 accuracy level) within two minutes using a single CPU core and about 6GB memory.
Dian Zhou - One of the best experts on this subject based on the ideXlab platform.
-
efficient Spectral graph sparsification via krylov subspace based Spectral Perturbation analysis
International Symposium on Circuits and Systems, 2017Co-Authors: Shuhan Zhang, Fan Yang, Xuan Zeng, Dian ZhouAbstract:Spectral graph sparsification aims to find an ultra-sparsified matrix which can be used as a good preconditioner for the original matrix. Low-stretch spanning tree could be constructed for this purpose. The relative condition number with the low-stretch spanning tree is bounded, which ensures the convergence of the PCG method with low-stretch spanning tree as preconditioner. Recently, Spectral Perturbation analysis is proposed to add a group of Spectral critical edges to the spanning tree. The relative condition number can thus be further reduced. In this paper, we proposed a Krylov-subspace based Spectral Perturbation analysis to find the Spectral critical edges. Compared with the traditional power-iteration-based approach, our proposed method can significantly improve the convergence of Spectral Perturbation analysis and thus accelerate the procedure of constructing the ultra-sparsified preconditioner.
-
ISCAS - Efficient Spectral graph sparsification via Krylov-subspace based Spectral Perturbation analysis
2017 IEEE International Symposium on Circuits and Systems (ISCAS), 2017Co-Authors: Shuhan Zhang, Fan Yang, Xuan Zeng, Dian ZhouAbstract:Spectral graph sparsification aims to find an ultra-sparsified matrix which can be used as a good preconditioner for the original matrix. Low-stretch spanning tree could be constructed for this purpose. The relative condition number with the low-stretch spanning tree is bounded, which ensures the convergence of the PCG method with low-stretch spanning tree as preconditioner. Recently, Spectral Perturbation analysis is proposed to add a group of Spectral critical edges to the spanning tree. The relative condition number can thus be further reduced. In this paper, we proposed a Krylov-subspace based Spectral Perturbation analysis to find the Spectral critical edges. Compared with the traditional power-iteration-based approach, our proposed method can significantly improve the convergence of Spectral Perturbation analysis and thus accelerate the procedure of constructing the ultra-sparsified preconditioner.
Ching Min Chang - One of the best experts on this subject based on the ideXlab platform.
-
Stochastic analysis of bounded unsaturated flow in heterogeneous aquifers: Spectral/Perturbation approach
Advances in Water Resources, 2009Co-Authors: Ching Min Chang, Hund-der YehAbstract:This paper describes a stochastic analysis of steady state flow in a bounded, partially saturated heterogeneous porous medium subject to distributed infiltration. The presence of boundary conditions leads to non-uniformity in the mean unsaturated flow, which in turn causes non-stationarity in the statistics of velocity fields. Motivated by this, our aim is to investigate the impact of boundary conditions on the behavior of field-scale unsaturated flow. Within the framework of Spectral theory based on Fourier– Stieltjes representations for the perturbed quantities, the general expressions for the pressure head variance, variance of log unsaturated hydraulic conductivity and variance of the specific discharge are presented in the wave number domain. Closed-form expressions are developed for the simplified case of statistical isotropy of the log hydraulic conductivity field with a constant soil pore-size distribution parameter. These expressions allow us to investigate the impact of the boundary conditions, namely the vertical infiltration from the soil surface and a prescribed pressure head at a certain depth below the soil surface. It is found that the boundary conditions are critical in predicting uncertainty in bounded unsaturated flow. Our analytical expression for the pressure head variance in a one-dimensional, heterogeneous flow domain, developed using a nonstationary Spectral representation approach [Li S-G,
-
The role of moisture fluctuations in unsaturated transport
Stochastic Hydrology and Hydraulics, 1997Co-Authors: Ching Min Chang, M. W. KemblowskiAbstract:Within the framework of stochastic theory and the Spectral Perturbation techniques, three-dimensional dispersion in partially saturated soils with a finite correlation scale of log-hydraulic conductivity is analyzed. The effects of spatial variability of the moisture distribution parameter on the asymptotic spreading behavior of a unsaturated solute plume are assessed. This is accomplished by comparing two asymptotic macrodispersivities and two variance of solute concentration, obtained for a constant moisture content and spatially varied moisture, respectively.
-
Stochastic analysis of two-phase flow in porous media: I. Spectral/Perturbation approach
Transport in Porous Media, 1995Co-Authors: Ching Min Chang, M. W. Kemblowski, Jagath J. Kaluarachchi, A. AbdinAbstract:Stochastic analysis of steady-state two-phase (water and oil) flow in heterogeneous porous media is performed using the Perturbation theory and Spectral representation techniques. The governing equations describing the flow are coupled and nonlinear. The key stochastic input variables are intrinsic permeability, k , and the soil and fluid dependent retention parameter, г. Three different stochastic combinations of these two imput parameters were considered. The Perturbation/Spectral analysis was used to develop closed-form expressions that describe stochastic variability of key output processes, such as capillary and individual phase pressures and specific discharges. The analysis also included the estimation of the effective flow properties. The impact of the spatial variability of k and г on the variances of pressures, effective conductivities, and specific discharges was examined.
Shuhan Zhang - One of the best experts on this subject based on the ideXlab platform.
-
efficient Spectral graph sparsification via krylov subspace based Spectral Perturbation analysis
International Symposium on Circuits and Systems, 2017Co-Authors: Shuhan Zhang, Fan Yang, Xuan Zeng, Dian ZhouAbstract:Spectral graph sparsification aims to find an ultra-sparsified matrix which can be used as a good preconditioner for the original matrix. Low-stretch spanning tree could be constructed for this purpose. The relative condition number with the low-stretch spanning tree is bounded, which ensures the convergence of the PCG method with low-stretch spanning tree as preconditioner. Recently, Spectral Perturbation analysis is proposed to add a group of Spectral critical edges to the spanning tree. The relative condition number can thus be further reduced. In this paper, we proposed a Krylov-subspace based Spectral Perturbation analysis to find the Spectral critical edges. Compared with the traditional power-iteration-based approach, our proposed method can significantly improve the convergence of Spectral Perturbation analysis and thus accelerate the procedure of constructing the ultra-sparsified preconditioner.
-
ISCAS - Efficient Spectral graph sparsification via Krylov-subspace based Spectral Perturbation analysis
2017 IEEE International Symposium on Circuits and Systems (ISCAS), 2017Co-Authors: Shuhan Zhang, Fan Yang, Xuan Zeng, Dian ZhouAbstract:Spectral graph sparsification aims to find an ultra-sparsified matrix which can be used as a good preconditioner for the original matrix. Low-stretch spanning tree could be constructed for this purpose. The relative condition number with the low-stretch spanning tree is bounded, which ensures the convergence of the PCG method with low-stretch spanning tree as preconditioner. Recently, Spectral Perturbation analysis is proposed to add a group of Spectral critical edges to the spanning tree. The relative condition number can thus be further reduced. In this paper, we proposed a Krylov-subspace based Spectral Perturbation analysis to find the Spectral critical edges. Compared with the traditional power-iteration-based approach, our proposed method can significantly improve the convergence of Spectral Perturbation analysis and thus accelerate the procedure of constructing the ultra-sparsified preconditioner.
Emilio Castellucci - One of the best experts on this subject based on the ideXlab platform.
-
Rotationally resolved electronic spectroscopy of aniline excited vibronic levels
Chemical Physics Letters, 2001Co-Authors: Giangaetano Pietraperzia, Maurizio Becucci, Ivan Del Pace, I. López-tocón, Emilio CastellucciAbstract:Abstract Experiments of molecular beam high resolution electronic spectroscopy were performed on several vibronic bands of the S1←S0 electronic transition of aniline. Here we report on the properties of the excited states with a vibrational energy up to 1300 cm−1 above the fundamental vibrational level of S1. The spectroscopic parameters of these levels, such as band centers and rotational constants, have been determined with high accuracy from the fit of more than 300 ro-vibronic transitions for each band. Each single ro-vibronic transition was found to be homogeneously broadened by about 18 MHz and no evidence of Spectral Perturbation was detected.
-
Rotationally resolved electronic spectroscopy of aniline excited vibronic levels
Chemical Physics Letters, 2001Co-Authors: Giangaetano Pietraperzia, Maurizio Becucci, Ivan Del Pace, I. López-tocón, Emilio CastellucciAbstract:Abstract Experiments of molecular beam high resolution electronic spectroscopy were performed on several vibronic bands of the S1←S0 electronic transition of aniline. Here we report on the properties of the excited states with a vibrational energy up to 1300 cm−1 above the fundamental vibrational level of S1. The spectroscopic parameters of these levels, such as band centers and rotational constants, have been determined with high accuracy from the fit of more than 300 ro-vibronic transitions for each band. Each single ro-vibronic transition was found to be homogeneously broadened by about 18 MHz and no evidence of Spectral Perturbation was detected.