The Experts below are selected from a list of 291 Experts worldwide ranked by ideXlab platform
P.k. Chan - One of the best experts on this subject based on the ideXlab platform.
-
Multilevel spectral hypergraph partitioning with Arbitrary Vertex sizes
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1999Co-Authors: J.y. Zien, M.d.f. Schlag, P.k. ChanAbstract:This paper presents a new spectral partitioning formulation which directly incorporates Vertex size information by modifying the Laplacian of the graph. Modifying the Laplacian produces a generalized eigenvalue problem, which is reduced to the standard eigenvalue problem. Experiments show that the scaled ratio-cut costs of results on benchmarks with Arbitrary Vertex size improve by 22% when the eigenvectors of the Laplacian in the spectral partitioner KP are replaced by the eigenvectors of our modified Laplacian. The inability to handle Vertex sizes in the spectral partitioning formulation has been a limitation in applying spectral partitioning in a multilevel setting. We investigate whether our new formulation effectively removes this limitation by combining it with a simple multilevel bottom-up clustering algorithm and an iterative improvement algorithm for partition refinement. Experiments show that in a multilevel setting where the spectral partitioner KP provides the initial partitions of the most contracted graph, using the modified Laplacian in place of the standard Laplacian is more efficient and more effective in the partitioning of graphs with Arbitrary-size and unit-size vertices; average improvements of 17% and 18% are observed for graphs with Arbitrary-size and unit-size vertices, respectively. Comparisons with other ratio-cut based partitioners on hypergraphs with unit-size as well as Arbitrary-size vertices, show that the multilevel spectral partitioner produces either better results or almost identical results more efficiently.
-
multi level spectral hypergraph partitioning with Arbitrary Vertex sizes
International Conference on Computer Aided Design, 1996Co-Authors: J.y. Zien, M.d.f. Schlag, P.k. ChanAbstract:This paper presents a new spectral partitioning formulation which directly incorporates Vertex size information by modifying the Laplacian of the graph. Modifying the Laplacian produces a generalized eigenvalue problem, which is reduced to the standard eigenvalue problem. Experiments show that the scaled ratio-cut costs of results on benchmarks with Arbitrary Vertex size improve by 22% when the eigenvectors of the Laplacian in the spectral partitioner KP are replaced by the eigenvectors of our modified Laplacian. The inability to handle Vertex sizes in the spectral partitioning formulation has been a limitation in applying spectral partitioning in a multilevel setting. We investigate whether our new formulation effectively removes this limitation by combining it with a simple multilevel bottom-up clustering algorithm and an iterative improvement algorithm for partition refinement. Experiments show that in a multilevel setting where the spectral partitioner KP provides the initial partitions of the most contracted graph, using the modified Laplacian in place of the standard Laplacian is more efficient and more effective in the partitioning of graphs with Arbitrary-size and unit-size vertices; average improvements of 17% and 18% are observed for graphs with Arbitrary-size and unit-size vertices, respectively. Comparisons with other ratio-cut based partitioners on hypergraphs with unit-size as well as Arbitrary-size vertices, show that the multilevel spectral partitioner produces either better results or almost identical results more efficiently.
-
ICCAD - Multi-level spectral hypergraph partitioning with Arbitrary Vertex sizes
1996Co-Authors: J.y. Zien, M.d.f. Schlag, P.k. ChanAbstract:This paper presents a new spectral partitioning formulation which directly incorporates Vertex size information by modifying the Laplacian of the graph. Modifying the Laplacian produces a generalized eigenvalue problem, which is reduced to the standard eigenvalue problem. Experiments show that the scaled ratio-cut costs of results on benchmarks with Arbitrary Vertex size improve by 22% when the eigenvectors of the Laplacian in the spectral partitioner KP are replaced by the eigenvectors of our modified Laplacian. The inability to handle Vertex sizes in the spectral partitioning formulation has been a limitation in applying spectral partitioning in a multilevel setting. We investigate whether our new formulation effectively removes this limitation by combining it with a simple multilevel bottom-up clustering algorithm and an iterative improvement algorithm for partition refinement. Experiments show that in a multilevel setting where the spectral partitioner KP provides the initial partitions of the most contracted graph, using the modified Laplacian in place of the standard Laplacian is more efficient and more effective in the partitioning of graphs with Arbitrary-size and unit-size vertices; average improvements of 17% and 18% are observed for graphs with Arbitrary-size and unit-size vertices, respectively. Comparisons with other ratio-cut based partitioners on hypergraphs with unit-size as well as Arbitrary-size vertices, show that the multilevel spectral partitioner produces either better results or almost identical results more efficiently.
-
Multi-level spectral hypergraph partitioning with Arbitrary Vertex sizes
Proceedings of International Conference on Computer Aided Design, 1996Co-Authors: J.y. Zien, M.d.f. Schlag, P.k. ChanAbstract:This paper presents a new spectral partitioning formation which directly incorporates Vertex size information. The new formulation results in a generalized eigenvalue problem, and this problem is reduced to the standard eigenvalue problem. Experimental results show that incorporating Vertex sizes into the eigenvalue calculation produces results that are 50% better than the standard formation in terms of scaled ratio-cut cost, even when a Kernighan-Lin style iterative improvement algorithm taking into account Vertex sizes is applied as a post-processing step. To evaluate the new method for use in multi-level partitioning, we combine the partitioner with a multi-level bottom-up clustering algorithm and an iterative improvement algorithm for partition refinement. Experimental results show that our new spectral algorithm is more effective than the standard spectral formulation and other partitioners in the multi-level partitioning of hypergraphs.
Tomas Akenine-möller - One of the best experts on this subject based on the ideXlab platform.
-
Automatic pre-tessellation culling
ACM Transactions on Graphics, 2009Co-Authors: Jon Hasselgren, Jacob Munkberg, Tomas Akenine-möllerAbstract:Graphics processing units supporting tessellation of curved surfaces with displacement mapping exist today. Still, to our knowledge, culling only occurs after tessellation, that is, after the base primitives have been tessellated into triangles. We introduce an algorithm for automatically computing tight positional and normal bounds on the fly for a base primitive. These bounds are derived from an Arbitrary Vertex shader program, which may include a curved surface evaluation and different types of displacements, for example. The obtained bounds are used for backface, view frustum, and occlusion culling before tessellation. For highly tessellated scenes, we show that up to 80p of the Vertex shader instructions can be avoided, which implies an “instruction speedup” of 5×. Our technique can also be used for offline software rendering.
-
Automatic pre-tessellation culling
ACM Transactions on Graphics, 2009Co-Authors: Jon Hasselgren, Jacob Munkberg, Tomas Akenine-möllerAbstract:Graphics processing units supporting tessellation of curved surfaces with displacement mapping exist today. Still, to our knowledge, culling only occurs after tessellation, that is, after the base primitives have been tessellated into triangles. We introduce an algorithm for automatically computing tight positional and normal bounds on the fly for a base primitive. These bounds are derived from an Arbitrary Vertex shader program, which may include a curved surface evaluation and different types of displacements, for example. The obtained bounds are used for backface, view frustum, and occlusion culling before tessellation. For highly tessellated scenes, we show that up to 80% of the Vertex shader instructions can be avoided, which implies an “instruction speedup” of 5×. Our technique can also be used for offline software rendering.
Yan Wang - One of the best experts on this subject based on the ideXlab platform.
-
Independent spanning trees on twisted cubes
Journal of Parallel and Distributed Computing, 2020Co-Authors: Yan Wang, Guodong ZhouAbstract:Multiple independent spanning trees have applications to fault tolerance and data broadcasting in distributed networks. There are two versions of the n independent spanning trees conjecture. The Vertex (edge) conjecture is that any n-connected (n-edge-connected) graph has n Vertex-independent spanning trees (edge-independent spanning trees) rooted at an Arbitrary Vertex. Note that the Vertex conjecture implies the edge conjecture. The Vertex and edge conjectures have been confirmed only for n-connected graphs with n@?4, and they are still open for Arbitrary n-connected graph when n>=5. In this paper, we confirm the Vertex conjecture (and hence also the edge conjecture) for the n-dimensional twisted cube TQ"n by providing an O(NlogN) algorithm to construct n Vertex-independent spanning trees rooted at any Vertex, where N denotes the number of vertices in TQ"n. Moreover, all independent spanning trees rooted at an Arbitrary Vertex constructed by our construction method are isomorphic and the height of each tree is n+1 for any integer n>=2.
-
An algorithm to construct independent spanning trees on parity cubes
Theoretical Computer Science, 2012Co-Authors: Yan Wang, He HuangAbstract:Independent spanning trees have applications in networks such as reliable communication protocols, one-to-all broadcasting, reliable broadcasting, and secure message distribution. Thus, the designs of independent spanning trees in several classes of networks have been widely investigated. However, there is a conjecture on independent spanning trees: any n-connected graph has n independent spanning trees rooted at an Arbitrary Vertex. This conjecture still remains open for n>=5. In this paper, by proposing an algorithm to construct n independent spanning trees rooted at any Vertex, we confirm the conjecture on n-dimensional parity cube PQ"n -- a variant of n-dimensional hypercube. Furthermore, we prove that all independent spanning trees rooted at an Arbitrary Vertex constructed by our construction method are isomorphic and the height of each tree is n+1 for any integer n>=2.
-
PAAP - An Algorithm to Find Optimal Independent Spanning Trees on Twisted-Cubes
2011 Fourth International Symposium on Parallel Architectures Algorithms and Programming, 2011Co-Authors: Yan WangAbstract:Multiple independent spanning trees have applications to fault tolerance and data broadcasting in distributed networks. There is a conjecture on independent spanning trees: any n-connected graph has n independent spanning trees rooted at an Arbitrary Vertex. The conjecture has been confirmed only for n-connected graphs with n=4, and it is still open for Arbitrary n-connected graphs when n ≥ 5. In this paper, we provide a construction algorithm to find n independent spanning trees for the n-dimensional twisted-cube TNn, where N denotes the number of vertices in TNn. And for n ≥ 3, the height of each indepen- dent spanning tree on TNn is n+1.
-
Construction of independent spanning trees on twisted-cubes
2011 IEEE International Conference on Computer Science and Automation Engineering, 2011Co-Authors: Yan WangAbstract:Multiple independent spanning trees have applications to fault-tolerant and data broadcasting in distributed networks. There is a conjecture on independent spanning trees: any n-connected graph has n independent spanning trees rooted at an Arbitrary Vertex. The conjecture has been confirmed only for n-connected graphs with n ≤ 4, and still open for Arbitrary n-connected graphs when n ≥ 5. In this paper, we confirm the conjecture for the n-dimensional twisted-cube TNn by providing an O(NlogN) algorithm to construct n independent spanning trees rooted at any Vertex, where N denotes the number of vertices in TNn.
-
An Algorithm to Find Optimal Independent Spanning Trees on Twisted-Cubes
2011 Fourth International Symposium on Parallel Architectures Algorithms and Programming, 2011Co-Authors: Yan WangAbstract:Multiple independent spanning trees have applications to fault tolerance and data broadcasting in distributed networks. There is a conjecture on independent spanning trees: any n-connected graph has n independent spanning trees rooted at an Arbitrary Vertex. The conjecture has been confirmed only for n-connected graphs with n=4, and it is still open for Arbitrary n-connected graphs when n ≥ 5. In this paper, we provide a construction algorithm to find n independent spanning trees for the n-dimensional twisted-cube TNn, where N denotes the number of vertices in TNn. And for n ≥ 3, the height of each independent spanning tree on TNn is n+1.
J.y. Zien - One of the best experts on this subject based on the ideXlab platform.
-
Multilevel spectral hypergraph partitioning with Arbitrary Vertex sizes
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1999Co-Authors: J.y. Zien, M.d.f. Schlag, P.k. ChanAbstract:This paper presents a new spectral partitioning formulation which directly incorporates Vertex size information by modifying the Laplacian of the graph. Modifying the Laplacian produces a generalized eigenvalue problem, which is reduced to the standard eigenvalue problem. Experiments show that the scaled ratio-cut costs of results on benchmarks with Arbitrary Vertex size improve by 22% when the eigenvectors of the Laplacian in the spectral partitioner KP are replaced by the eigenvectors of our modified Laplacian. The inability to handle Vertex sizes in the spectral partitioning formulation has been a limitation in applying spectral partitioning in a multilevel setting. We investigate whether our new formulation effectively removes this limitation by combining it with a simple multilevel bottom-up clustering algorithm and an iterative improvement algorithm for partition refinement. Experiments show that in a multilevel setting where the spectral partitioner KP provides the initial partitions of the most contracted graph, using the modified Laplacian in place of the standard Laplacian is more efficient and more effective in the partitioning of graphs with Arbitrary-size and unit-size vertices; average improvements of 17% and 18% are observed for graphs with Arbitrary-size and unit-size vertices, respectively. Comparisons with other ratio-cut based partitioners on hypergraphs with unit-size as well as Arbitrary-size vertices, show that the multilevel spectral partitioner produces either better results or almost identical results more efficiently.
-
multi level spectral hypergraph partitioning with Arbitrary Vertex sizes
International Conference on Computer Aided Design, 1996Co-Authors: J.y. Zien, M.d.f. Schlag, P.k. ChanAbstract:This paper presents a new spectral partitioning formulation which directly incorporates Vertex size information by modifying the Laplacian of the graph. Modifying the Laplacian produces a generalized eigenvalue problem, which is reduced to the standard eigenvalue problem. Experiments show that the scaled ratio-cut costs of results on benchmarks with Arbitrary Vertex size improve by 22% when the eigenvectors of the Laplacian in the spectral partitioner KP are replaced by the eigenvectors of our modified Laplacian. The inability to handle Vertex sizes in the spectral partitioning formulation has been a limitation in applying spectral partitioning in a multilevel setting. We investigate whether our new formulation effectively removes this limitation by combining it with a simple multilevel bottom-up clustering algorithm and an iterative improvement algorithm for partition refinement. Experiments show that in a multilevel setting where the spectral partitioner KP provides the initial partitions of the most contracted graph, using the modified Laplacian in place of the standard Laplacian is more efficient and more effective in the partitioning of graphs with Arbitrary-size and unit-size vertices; average improvements of 17% and 18% are observed for graphs with Arbitrary-size and unit-size vertices, respectively. Comparisons with other ratio-cut based partitioners on hypergraphs with unit-size as well as Arbitrary-size vertices, show that the multilevel spectral partitioner produces either better results or almost identical results more efficiently.
-
ICCAD - Multi-level spectral hypergraph partitioning with Arbitrary Vertex sizes
1996Co-Authors: J.y. Zien, M.d.f. Schlag, P.k. ChanAbstract:This paper presents a new spectral partitioning formulation which directly incorporates Vertex size information by modifying the Laplacian of the graph. Modifying the Laplacian produces a generalized eigenvalue problem, which is reduced to the standard eigenvalue problem. Experiments show that the scaled ratio-cut costs of results on benchmarks with Arbitrary Vertex size improve by 22% when the eigenvectors of the Laplacian in the spectral partitioner KP are replaced by the eigenvectors of our modified Laplacian. The inability to handle Vertex sizes in the spectral partitioning formulation has been a limitation in applying spectral partitioning in a multilevel setting. We investigate whether our new formulation effectively removes this limitation by combining it with a simple multilevel bottom-up clustering algorithm and an iterative improvement algorithm for partition refinement. Experiments show that in a multilevel setting where the spectral partitioner KP provides the initial partitions of the most contracted graph, using the modified Laplacian in place of the standard Laplacian is more efficient and more effective in the partitioning of graphs with Arbitrary-size and unit-size vertices; average improvements of 17% and 18% are observed for graphs with Arbitrary-size and unit-size vertices, respectively. Comparisons with other ratio-cut based partitioners on hypergraphs with unit-size as well as Arbitrary-size vertices, show that the multilevel spectral partitioner produces either better results or almost identical results more efficiently.
-
Multi-level spectral hypergraph partitioning with Arbitrary Vertex sizes
Proceedings of International Conference on Computer Aided Design, 1996Co-Authors: J.y. Zien, M.d.f. Schlag, P.k. ChanAbstract:This paper presents a new spectral partitioning formation which directly incorporates Vertex size information. The new formulation results in a generalized eigenvalue problem, and this problem is reduced to the standard eigenvalue problem. Experimental results show that incorporating Vertex sizes into the eigenvalue calculation produces results that are 50% better than the standard formation in terms of scaled ratio-cut cost, even when a Kernighan-Lin style iterative improvement algorithm taking into account Vertex sizes is applied as a post-processing step. To evaluate the new method for use in multi-level partitioning, we combine the partitioner with a multi-level bottom-up clustering algorithm and an iterative improvement algorithm for partition refinement. Experimental results show that our new spectral algorithm is more effective than the standard spectral formulation and other partitioners in the multi-level partitioning of hypergraphs.
Jon Hasselgren - One of the best experts on this subject based on the ideXlab platform.
-
Automatic pre-tessellation culling
ACM Transactions on Graphics, 2009Co-Authors: Jon Hasselgren, Jacob Munkberg, Tomas Akenine-möllerAbstract:Graphics processing units supporting tessellation of curved surfaces with displacement mapping exist today. Still, to our knowledge, culling only occurs after tessellation, that is, after the base primitives have been tessellated into triangles. We introduce an algorithm for automatically computing tight positional and normal bounds on the fly for a base primitive. These bounds are derived from an Arbitrary Vertex shader program, which may include a curved surface evaluation and different types of displacements, for example. The obtained bounds are used for backface, view frustum, and occlusion culling before tessellation. For highly tessellated scenes, we show that up to 80p of the Vertex shader instructions can be avoided, which implies an “instruction speedup” of 5×. Our technique can also be used for offline software rendering.
-
Automatic pre-tessellation culling
ACM Transactions on Graphics, 2009Co-Authors: Jon Hasselgren, Jacob Munkberg, Tomas Akenine-möllerAbstract:Graphics processing units supporting tessellation of curved surfaces with displacement mapping exist today. Still, to our knowledge, culling only occurs after tessellation, that is, after the base primitives have been tessellated into triangles. We introduce an algorithm for automatically computing tight positional and normal bounds on the fly for a base primitive. These bounds are derived from an Arbitrary Vertex shader program, which may include a curved surface evaluation and different types of displacements, for example. The obtained bounds are used for backface, view frustum, and occlusion culling before tessellation. For highly tessellated scenes, we show that up to 80% of the Vertex shader instructions can be avoided, which implies an “instruction speedup” of 5×. Our technique can also be used for offline software rendering.
