The Experts below are selected from a list of 306 Experts worldwide ranked by ideXlab platform

Cevdet Aykanat - One of the best experts on this subject based on the ideXlab platform.

  • The Effect of Various Sparsity Structures on Parallelism and Algorithms to Reveal Those Structures
    Parallel Algorithms in Computational Science and Engineering, 2020
    Co-Authors: Oguz Selvitopi, Seher Acer, Murat Manguoglu, Cevdet Aykanat
    Abstract:

    Structured sparse matrices can greatly benefit parallel numerical methods in terms of parallel perFormance and convergence. In this chapter, we present combinatorial models for obtaining several different sparse matrix Forms. There are four basic Forms we focus on: singly-bordered Block-Diagonal Form, doubly-bordered Block-Diagonal Form, nonempty off-Diagonal Block minimization, and Block Diagonal with overlap Form. For each of these Forms, we first present the Form in detail and describe what goals are sought within the Form, and then examine the combinatorial models that attain the respective Form while targeting the sought goals, and finally explain in which aspects the Forms benefit certain parallel numerical methods and their relationship with the models. Our work focuses especially on graph and hypergraph partitioning models in obtaining the mentioned Forms. Despite their relatively high preprocessing overhead compared to other heuristics, they have proven to model the given problem more accurately and this overhead can be often amortized due the fact that matrix structure does not change much during a typical numerical simulation. This chapter presents a number of models and their relationship with parallel numerical methods.

  • a recursive bipartitioning algorithm for permuting sparse square matrices into Block Diagonal Form with overlap
    SIAM Journal on Scientific Computing, 2013
    Co-Authors: Seher Acer, Enver Kayaaslan, Cevdet Aykanat
    Abstract:

    We investigate the problem of symmetrically permuting a square sparse matrix into a Block Diagonal Form with overlap. This permutation problem arises in the parallelization of an explicit Formulation of the multiplicative Schwarz preconditioner and a more recent Block overlapping banded linear solver as well as its application to general sparse linear systems. In order to Formulate this permutation problem as a graph theoretical problem, we define a constrained version of the multiway graph partitioning by vertex separator (GPVS) problem, which is referred to as the ordered GPVS (oGPVS) problem. However, existing graph partitioning tools are unable to solve the oGPVS problem. So, we also show how the recursive bipartitioning framework can be utilized for solving the oGPVS problem. For this purpose, we propose a left-to-right bipartitioning approach together with a novel vertex fixation scheme so that existing 2-way GPVS tools that support fixed vertices can be effectively and efficiently utilized in the r...

  • A Recursive Bipartitioning Algorithm for Permuting Sparse Square Matrices into Block Diagonal Form with Overlap
    SIAM Journal on Scientific Computing, 2013
    Co-Authors: Seher Acer, Enver Kayaaslan, Cevdet Aykanat
    Abstract:

    We investigate the problem of symmetrically permuting a square sparse matrix into a Block Diagonal Form with overlap. This permutation problem arises in the parallelization of an explicit Formulation of the multiplicative Schwarz preconditioner and a more recent Block overlapping banded linear solver as well as its application to general sparse linear systems. In order to Formulate this permutation problem as a graph theoretical problem, we define a constrained version of the multiway graph partitioning by vertex separator (GPVS) problem, which is referred to as the ordered GPVS (oGPVS) problem. However, existing graph partitioning tools are unable to solve the oGPVS problem. So, we also show how the recursive bipartitioning framework can be utilized for solving the oGPVS problem. For this purpose, we propose a left-to-right bipartitioning approach together with a novel vertex fixation scheme so that existing 2-way GPVS tools that support fixed vertices can be effectively and efficiently utilized in the recursive bipartitioning framework. Experimental results on a wide range of matrices confirm the validity of the proposed approach. © 2013 Society for Industrial and Applied Mathematics

  • Permuting Sparse Rectangular Matrices into Block-Diagonal Form
    SIAM Journal on Scientific Computing, 2004
    Co-Authors: Cevdet Aykanat, Ali Pinar, Ümit V. Çatalyürek
    Abstract:

    We investigate the problem of permuting a sparse rectangular matrix into Block-Diagonal Form. Block-Diagonal Form of a matrix grants an inherent parallelism for solving the deriving problem, as recently investigated in the context of mathematical programming, LU factorization, and QR factorization. To represent the nonzero structure of a matrix, we propose bipartite graph and hypergraph models that reduce the permutation problem to those of graph partitioning by vertex separator and hypergraph partitioning, respectively. Our experiments on a wide range of matrices, using the state-of-the-art graph and hypergraph partitioning tools MeTiS and PaToH\@, revealed that the proposed methods yield very effective solutions both in terms of solution quality and runtime.

Elena Yegorova - One of the best experts on this subject based on the ideXlab platform.

  • Block Diagonal Form of distance matrix for region based image retrieval
    International Conference on Pattern Recognition, 2008
    Co-Authors: Dmitry Kinoshenko, Vladimir Mashtalir, Elena Yegorova
    Abstract:

    There are two substantial open issues in the field of the image retrieval: semantic gap between computationally extracted low-level features and human operated high-level concepts, and high retrieval speed independent from the volume of the database. Search of the images on the level of objects or regions (segmentation) is a step towards semantic-based retrieval. In this paper we propose a new cluster-like indexing algorithm in metric space which preliminary transForms distance matrix into Block-Diagonal Form and ensures the minimum number of matches at the retrieval stage. This Form can be used separately or embedded into existent indexing methods.

  • ICPR - Block-Diagonal Form of distance matrix for region-based image retrieval
    2008 19th International Conference on Pattern Recognition, 2008
    Co-Authors: Dmitry Kinoshenko, Vladimir Mashtalir, Elena Yegorova
    Abstract:

    There are two substantial open issues in the field of the image retrieval: semantic gap between computationally extracted low-level features and human operated high-level concepts, and high retrieval speed independent from the volume of the database. Search of the images on the level of objects or regions (segmentation) is a step towards semantic-based retrieval. In this paper we propose a new cluster-like indexing algorithm in metric space which preliminary transForms distance matrix into Block-Diagonal Form and ensures the minimum number of matches at the retrieval stage. This Form can be used separately or embedded into existent indexing methods.

Hendriks R.c. - One of the best experts on this subject based on the ideXlab platform.

  • Distributed Rate-Constrained LCMV BeamForming
    'Institute of Electrical and Electronics Engineers (IEEE)', 2019
    Co-Authors: Zhang J., Koutrouvelis A., Heusdens R., Hendriks R.c.
    Abstract:

    In this letter, we propose a decentralized framework for rate-distributed linearly constrained minimum variance (LCMV) beamForming in wireless acoustic sensor networks. To save the energy usage within the network, we propose to minimize the transmission cost and put a constraint on the noise reduction perFormance. Subsequently, we decentralize the obtained LCMV filter structure by exploiting an imposed Block Diagonal Form of the noise correlation matrix. As a result, the beamFormer weights are calculated in a decentralized fashion and each node can determine its quantization rate locally. Finally, numerical results validate the proposed method.Circuits and System

  • A Low-Cost Robust Distributed Linearly Constrained BeamFormer for Wireless Acoustic Sensor Networks with Arbitrary Topology
    2018
    Co-Authors: Koutrouvelis A., Heusdens R., Sherson T.w., Hendriks R.c.
    Abstract:

    We propose a new robust distributed linearly constrained beamFormer which utilizes a set of linear equality constraints to reduce the cross power spectral density matrix to a Block-Diagonal Form. The proposed beamFormer has a convenient objective function for use in arbitrary distributed network topologies while having identical perFormance to a centralized implementation. Moreover, the new optimization problem is robust to relative acoustic transfer function (RATF) estimation errors and to target activity detection (TAD) errors. Two variants of the proposed beamFormer are presented and evaluated in the context of multi-microphone speech enhancement in a wireless acoustic sensor network, and are compared with other state-of-the-art distributed beamFormers in terms of communication costs and robustness to RATF estimation errors and TAD errors.

  • A Low-Cost Robust Distributed Linearly Constrained BeamFormer for Wireless Acoustic Sensor Networks with Arbitrary Topology
    'Institute of Electrical and Electronics Engineers (IEEE)', 2018
    Co-Authors: Koutrouvelis A., Heusdens R., Sherson T.w., Hendriks R.c.
    Abstract:

    We propose a new robust distributed linearly constrained beamFormer which utilizes a set of linear equality constraints to reduce the cross power spectral density matrix to a Block-Diagonal Form. The proposed beamFormer has a convenient objective function for use in arbitrary distributed network topologies while having identical perFormance to a centralized implementation. Moreover, the new optimization problem is robust to relative acoustic transfer function (RATF) estimation errors and to target activity detection (TAD) errors. Two variants of the proposed beamFormer are presented and evaluated in the context of multi-microphone speech enhancement in a wireless acoustic sensor network, and are compared with other state-of-the-art distributed beamFormers in terms of communication costs and robustness to RATF estimation errors and TAD errors.Circuits and System

Dmitry Kinoshenko - One of the best experts on this subject based on the ideXlab platform.

  • Block Diagonal Form of distance matrix for region based image retrieval
    International Conference on Pattern Recognition, 2008
    Co-Authors: Dmitry Kinoshenko, Vladimir Mashtalir, Elena Yegorova
    Abstract:

    There are two substantial open issues in the field of the image retrieval: semantic gap between computationally extracted low-level features and human operated high-level concepts, and high retrieval speed independent from the volume of the database. Search of the images on the level of objects or regions (segmentation) is a step towards semantic-based retrieval. In this paper we propose a new cluster-like indexing algorithm in metric space which preliminary transForms distance matrix into Block-Diagonal Form and ensures the minimum number of matches at the retrieval stage. This Form can be used separately or embedded into existent indexing methods.

  • ICPR - Block-Diagonal Form of distance matrix for region-based image retrieval
    2008 19th International Conference on Pattern Recognition, 2008
    Co-Authors: Dmitry Kinoshenko, Vladimir Mashtalir, Elena Yegorova
    Abstract:

    There are two substantial open issues in the field of the image retrieval: semantic gap between computationally extracted low-level features and human operated high-level concepts, and high retrieval speed independent from the volume of the database. Search of the images on the level of objects or regions (segmentation) is a step towards semantic-based retrieval. In this paper we propose a new cluster-like indexing algorithm in metric space which preliminary transForms distance matrix into Block-Diagonal Form and ensures the minimum number of matches at the retrieval stage. This Form can be used separately or embedded into existent indexing methods.

Kiyohiro Ikeda - One of the best experts on this subject based on the ideXlab platform.

  • Efficient TransFormation for Block-Diagonalization
    Imperfect Bifurcation in Structures and Materials, 2010
    Co-Authors: Kiyohiro Ikeda, Kazuo Murota
    Abstract:

    Group representation theory guarantees that the Jacobian matrix of symmetric systems can be transFormed to a Block-Diagonal Form (cf., §7.7.1). This chapter presents an efficient computational method for this Block-Diagonalization.

  • Block-DiagonalIZATION METHOD FOR SYMMETRIC STRUCTURES WITH ROTATIONAL DISPLACEMENTS
    Doboku Gakkai Ronbunshu, 1994
    Co-Authors: Ichiro Ario, Kiyohiro Ikeda, Kazuo Murota
    Abstract:

    The group-representation theory guarantees that the (tangent) stiffness matrix of symmetric structures can be put into a Block-Diagonal Form by means of a suitable (local) geometric transFormation. This transFormation decomposes the linear equilibrium equation of symmetric structures into a number of independent equations, and hence is advantageous for parallel analysis. The Block-Diagonalization method, which so far has mainly been applied for translational displacements, is extended here to rotational ones. The interrelationship between the symmetries of rotational and translational displacements is investigated by means of group theory to arrive at the transFormation matrix of rotational ones.

  • Block-Diagonalization analysis of symmetric plates
    International Journal of Solids and Structures, 1992
    Co-Authors: Kiyohiro Ikeda, Ichiro Ario, Kunio Torii
    Abstract:

    Abstract This paper presents a Block-Diagonalization method to solve stiffness equations of isotropic symmetric plates. By means of a suitable “local” coordinate transFormation, chosen based on group theory, the stiffness matrix is decomposed into a Block-Diagonal Form. The stiffness equation in the local coordinate is solved Block by Block, thus realizing numerical efficiency and greatly reducing the requisite amount of computer memory. The efficiency has been further upgraded with the aid of the concept of augmented orbit. This method is applied to a square isotropic plate subject to “asymmetric” loads to show its usefulness.