Search

A matrix is homogeneous if all of its entries are equal. Let $P$ be a $2\times 2$ zero-one matrix that is not homogeneous. We prove that if an $n\times n$ zero-one matrix $A$ does not contain $P$ as a submatrix, then $A$ has an $cn\times cn$ homogeneous submatrix for a suitable constant $c>0$. We further provide an almost complete characterization of the matrices $P$ (missing only finitely many cases) such that forbidding $P$ in $A$ guarantees an $n^{1-o(1)}\times n^{1-o(1)}$ homogeneous submatrix. We apply our results to chordal bipartite graphs, totally balanced matrices, halfplane-arrangements and string graphs., 21 pages, 2 figures. Revised version, a tabular overview of results added at the end

As an effective structure health monitoring technology, acoustic emission (AE) has been developed rapidly in various fields over recent years. AE source localization is the core element of AE technology. In this paper, a Node Block Location Method (NBLM) based on the collaborative model of node and block matrix was proposed to meet the high-precision requirement of source localization in the quasi-cylindrical structure with complex hole. NBLM can not only bypass the empty area, but also fit the actual propagation of elastic waves better in the complex boundaries. In order to evaluate the effectiveness of NBLM, lead-breaking tests were carried out on two cylindrical structure: one with square hole and the other with circular hole. The lead-breaking points were used as AE source in the test. The source coordinates were inverted by three separate location methods according to arrivals. Test results verify the superiority of NBLM and show that the location accuracy of the NBLM has been greatly improved compared to the existing methods.

In this paper we prove the strong consistency of several methods based on the spectral clustering techniques that are widely used to study the community detection problem in stochastic block models (SBMs). We show that under some weak conditions on the minimal degree, the number of communities, and the eigenvalues of the probability block matrix, the K-means algorithm applied to the eigenvectors of the graph Laplacian associated with its first few largest eigenvalues can classify all individuals into the true community uniformly correctly almost surely. Extensions to both regularized spectral clustering and degree-corrected SBMs are also considered. We illustrate the performance of different methods on simulated networks., 64 pages

We present a partition of unity finite element method for wave propagation problems in the time domain using an explicit time integration scheme. Plane wave enrichment functions are introduced at the finite elements nodes which allows for a coarse mesh at low order polynomial shape functions even at high wavenumbers. The initial condition is formulated as a Galerkin approximation in the enriched function space. We also show the possibility of lumping the mass matrix which is approximated as a block diagonal system. The proposed method, with and without lumping, is validated using three test cases and compared to an implicit time integration approach. The stability of the proposed approach against different factors such as the choice of wavenumber for the enrichment functions, the spatial discretization, the distortions in mesh elements or the timestep size, is tested in the numerical studies. The method performance is measured for the solution accuracy and the CPU processing times. The results show significant advantages for the proposed lumping approach which outperforms other considered approaches in terms of stability. Furthermore, the resulting block diagonal system only requires a fraction of the CPU time needed to solve the full system associated with the non-lumped approaches.

In this paper, a robust and effective preconditioner for the fast Method of Moments(MoM) based Hierarchal Electric Field Integral Equation(EFIE) solver is proposed using symmetric near-field Schur's complement method. In this preconditioner, near-field blocks are scaled to a diagonal block matrix and these near-field blocks are replaced with the scaled diagonal block matrix which reduces the near-field storage memory and the overall matrix vector product time. Scaled diagonal block matrix is further used as a preconditioner and due to the block diagonal form of the final preconditioner, no additional fill-ins are introduced in its inverse. The symmetric property of the near-field blocks is exploited to reduce the preconditioner setup time. Near linear complexity of preconditioner set up and solve times is achieved by near-field block ordering, using graph bandwidth reduction algorithms and compressing the fill-in blocks in preconditioner computation. Preconditioner set up time is reduced to half by using the symmetric property and near-field block ordering. It has been shown using a complexity analysis that the cost of preconditioner construction in terms of computation and memory is linear. Numerical experiments demonstrate an average of 1.5-2.3x speed-up in the iterative solution time over Null-Field based preconditioners.

This article puts forward a computationally efficient block matrix based precise integration algorithm for solving vibration response subjected to time-variable excitation and nonlinearity, especially for nonhomogeneous dynamic response solution with large-scale degrees-of-freedom. In detail, the nonlinear parts and time-varying inputs of a dynamic system are separated from the original dynamic equations and then simulated within a computing time-step by employing a piecewise interpolation function. A novel closed-form iteration formula is presented in conjunction with the block matrix strategy and modified increment-dimensional precise integration technique. Interestingly, the presented approach is essentially a high-accuracy and parallel algorithm, which exhibits a high prediction accuracy without the limitation of matrix inversion, higher-order derivative, periodicity requirement nor cycle oscillation and instability of high-order interpolation. The feasibility and advantage of the proposed method are verified with two numerical examples.

A new method of kinematic analysis and singularity analysis is proposed for a 7-DOF redundant manipulator with three consecutive parallel axes. First, the redundancy angle is described according to the self-motion characteristics of the manipulator, the position and orientation of the end-effector are separated, and the inverse kinematics of this manipulator is analyzed by geometric methods with the redundancy angle as a constraint. Then, the Jacobian matrix is established to derive the conditions for the kinematic singularities of the robotic arm by using the primitive matrix method and the block matrix method. Then, the kinematic singularities conditions in the joint space are mapped to the Cartesian space, and the singular configuration is described using the end poses and redundancy angles of the robotic arm, and a singularity avoidance method based on the redundancy angles and end pose is proposed. Finally, the correctness and feasibility of the inverse kinematics algorithm and the singularity avoidance method are verified by simulation examples.

Finding four six-dimensional mutually unbiased bases (MUBs) containing the identity matrix is a long-standing open problem in quantum information. We show that if they exist, then the $H_2$-reducible matrix in the four MUBs has exactly nine $2\times2$ Hadamard submatrices. We apply our result to exclude from the four MUBs some known CHMs, such as symmetric $H_2$-reducible matrix, the Hermitian matrix, Dita family, Bjorck's circulant matrix, and Szollosi family. Our results represent the latest progress on the existence of six-dimensional MUBs., 15 pages, be published on quantum information processing. arXiv admin note: text overlap with arXiv:1904.10181

Reducing the cost of implementing phasor measurement units (PMUs) can be achieved by determining the minimum number of devices needed to provide the electrical network observability. This article describes the optimal PMU placement algorithm, based on the analysis of the topological properties of the electrical network. It was shown that the optimal placement of PMUs can be achieved by dividing the nodal admittance matrix into four submatrices, one of them will be a band submatrix, which can be reduced to a lower triangular matrix of maximum rank by elementary transformations. Results reflecting the number of installed PMUs were obtained for IEEE test bus systems with 9, 14, 19, 30 and 57 nodes. For all test bus systems, the proposed PMU placement algorithm provides complete observability of the system with the same or fewer nodes of installation in comparison with the results of other authors. There were carried out computations with the help of the algorithm accelerated calculations of state estimation performance in power systems, in order to confirm the correctness of this approach. There were determined conditions under which the equations of nodal voltages were solved linearly and nonlinearly (iteratively).

This note is partly expositor). Inequalities relating inversion with, respectively, extraction of principal submatriees and the Hadamard product in the two possible orders are developed in a simple and unified way for positive definite matrices. These inequalities are known, hut we also characterize the cases of equality and strict inequality. A by-product is, for example, a pleasant proof of an inequality due to Fiedler. In addition, it is shown that the Hadamard product preserves inequalities in a generalization of Schur's observation. In the process, many tools for dealing with the positive semi-definite partial ordering are exhibited.

International audience; First, an acceleration to compute the impedance matrix obtained from the EFIE (electric field integral equation) discretized by the Galerkin MoM (method of moments) with Rao-Wilton-Glisson basis functions, is addressed. It is based on a far-field approximation and makes it possible to avoid to loop on the source and observation triangles. Next, the impedance matrix is split into strong and weak interactions; the latter is compressed by expressing it from Toeplitz sub-matrices. Then, the linear system is efficiently solved by a bi-iterative scheme. For a given order, the LSQR (least squares QR) algorithm is applied to solve the sparse linear system related to the strong interactions, while the matrix-vector products, related to the weak interactions, are accelerated by using FFTs. Numerical results of the field scattered by perfectly-conducting paraboloid-shape object and Gaussian rough surface are shown.

We present a computationally efficient approach to perform systematically convergent real-space all-electron Kohn-Sham density functional theory calculations for solids using an enriched finite element (FE) basis. The enriched FE basis is constructed by augmenting the classical FE basis with atom-centered numerical basis functions, comprising of atomic solutions to the Kohn-Sham problem. Notably, to improve the conditioning, we orthogonalize the enrichment functions with respect to the classical FE basis, without sacrificing the locality of the resultant basis. In addition to improved conditioning, this orthogonalization procedure also renders the overlap matrix block diagonal, greatly simplifying its inversion. Subsequently, we use a Chebyshev polynomial based filtering technique to efficiently compute the occupied eigenspace in each self-consistent field iteration. We demonstrate the accuracy and efficiency of the proposed approach on periodic unit cells and supercells. The benchmark studies show a staggering $130\ifmmode\times\else\texttimes\fi{}$ speedup of the orthogonalized enriched FE basis over the classical FE basis. We also present a comparison of the orthogonalized enriched FE basis with the linearized augmented plane-wave $+$ local orbitals basis, both in terms of accuracy and efficiency. Notably, we demonstrate that the orthogonalized enriched FE basis can handle large system sizes of $\ensuremath{\sim}10\phantom{\rule{0.16em}{0ex}}000$ electrons. Finally, we observe good parallel scalability of our implementation with $92%$ efficiency at $22\ifmmode\times\else\texttimes\fi{}$ speedup for a system with 620 electrons.

In recent years, discontinuous Galerkin time-domain (DGTD) method has found widespread use in computational electromagnetics [1]-[2]. This is due to the fact that it combines the advantages of finite-element and finite-volume methods (FEM and FVM). Just like FEM, it allows for accurate representation of the geometry and uses higher- order basis functions. Like FVM, it uses numerical flux to realize information exchange between discretization elements localizing all spatial operations. This yields a block diagonal mass matrix, where the dimension of each block is equal to the degrees of freedom in each element. The inverse of mass matrix is computed block by block and stored before the time marching starts. Using an explicit integrator to execute the time marching results in a very efficient and compact DGTD solver. Indeed, high-order (explicit) Runge-Kutta (RK) methods are often incorporated with DG frameworks making use of nodal high-order polynomial basis functions to solve Maxwell equations [2].

In this paper, a fast direct solver based on strong admissibility skeletonization factorization (SASF) and Poggio-Miller-Chang-Harrington-Wu-Tsai (PMCHWT) is proposed for electromagnetic scattering from conducting objects. Different from weak admissibility skeletonization scheme, the proposed method constructs the sparse-data representation, in which interactions of well-separated groups are compressed by low-rank algorithm. As a result, the approximation rank is relatively small, and the computational efficiency will have significant improvement. Subsequently, SASF is applied to the compressed system matrix. The system matrix can be factorized into products of a series of block unit triangular matrices and a block diagonal matrix. The arising fill-in blocks corresponding to far-field interactions are compressed and eliminated by a novel and efficient method to maintain the high efficiency and accuracy of the factorization procedure. The computational complexity and storage requirement of proposed factorization scale as $O(N^{1.5})$ and $O(N\log N)$ , respectively. Several numerical results are presented to demonstrate the accuracy and effectiveness of the proposed method.

Domain decomposition of the network conductance matrix is one of the efficient approaches to solve large-scale networks in parallel, wherein the most commonly-used non-iterative method is the Schur complement (SC) method. However, the SC method could not obtain the network conductance matrix inversion directly, and the computational cost will increase fast when the overlapping domain expands. In this work, a novel Linking-Domain Extraction (LDE) based decomposition method is proposed, in which the network matrix is expressed as the sum of a linking-domain matrix (LDM) and a diagonal block matrix (DBM) composed of multiple block matrices in diagonal. Through mathematical analysis over LDM, one lemma about the nature of LDM and its proof are proposed. Based on this lemma, the general formulation of the inverse matrix of the sum of LDM and DBM can be found using the Woodbury matrix identity, and based on the formulation the network matrix inversion can be directly computed in parallel to significantly accelerate the matrix inversion process. Test systems were implemented on both the FPGA and GPU parallel architectures, and the simulation results and speed-ups over the SC method and Gauss-Jordan elimination demonstrate the validity and efficiency of the proposed LDE method.

A method of uncertainty quantification on a quantum circuit using three samples for the Rh(111)-catalyzed CO oxidation reaction is demonstrated. Three parametrized samples of a reduced, linearized microkinetic model populate a single block diagonal matrix for a quantum circuit. This approach leverages the logarithmic scaling of the number of qubits with respect to matrix size. The Harrow, Hassidim, and Lloyd (HHL) algorithm for solving linear systems is employed, and the results are compared with the classical results. This application area of uncertainty quantification in chemical kinetics can experience a quantum advantage using the method reported here, although issues related to larger systems are discussed.

Distributed matrix computations over large clusters can suffer from the problem of slow or failed worker nodes (called stragglers) which can dominate the overall job execution time. Coded computation utilizes concepts from erasure coding to mitigate the effect of stragglers by running 'coded' copies of tasks comprising a job; stragglers are typically treated as erasures. While this is useful, there are issues with applying, e.g., MDS codes in a straightforward manner. Several practical matrix computation scenarios involve sparse matrices. MDS codes typically require dense linear combinations of submatrices of the original matrices which destroy their inherent sparsity. This is problematic as it results in significantly higher worker computation times. Moreover, treating slow nodes as erasures ignores the potentially useful partial computations performed by them. Furthermore, some MDS techniques also suffer from significant numerical stability issues. In this work we present schemes that allow us to leverage partial computation by stragglers while imposing constraints on the level of coding that is required in generating the encoded submatrices. This significantly reduces the worker computation time as compared to previous approaches and results in improved numerical stability in the decoding process. Exhaustive numerical experiments on Amazon Web Services (AWS) clusters support our findings.

We develop an efficient method for solving transport equations, particularly in the context of electroweak baryogenesis. It provides fully-analytical results under mild approximations and can also test semi-analytical results, which are applicable in more general cases. Key elements of our method include the reduction of the second-order differential equations to first order, representing the set of coupled equations as a block matrix of the particle densities and their derivatives, identification of zero modes, and block decomposition of the matrix. We apply our method to calculate the baryon asymmetry of the Universe (BAU) in a Standard Model effective field theory framework of complex Yukawa couplings to determine the sensitivity of the resulting BAU to modifications of various model parameters and rates, and to estimate the effect of the commonly-used thin-wall approximation., 23 pages + 3 appendices, 9 figures, 4 tables

In this paper, we propose a novel incomplete multi-view clustering method, in which a tensor nuclear norm regularizer elegantly diffuses the information of multi-view block-diagonal structure across different views. By exploring the membership between observed and missing samples and that between missing ones in each incomplete view with the guidance of the high-order view consistency, a global block-diagonal structure is well preserved in multiple spectral embedding matrices. Meanwhile, a consensus representation with strong separability is obtained for clustering. An iterative algorithm based on Augmented Lagrange Multiplier (ALM) is designed to solve the resultant model. Experimental results on six benchmark datasets indicate the superiority of the proposed method. http://github.com/ChangTang/TMBSD

Predmet istraživanja ove doktorske disertacije je sistematsko povezivanjedinamičkih svojstava kompleksnih sistema (kao što su stabilnost, robusnost, reaktivnost, tranziciono ponašanje, amplifikacioni okvir) sa teorijom H-matrica, koje je motivisalo nove rezultate iz oblasti lokalizacije blok i frakcionog pseudospektra, kao i ocene norme inverzne matrice, kako u tačkastoj, tako i u blok formi, ali i primenu ovih rezultata u dinamičkoj analizi kompleksnih sistema., This thesis provides a systematic link between the dynamical properties of complex systems (such as stability, robustness, reactivity, transient behavior, amplification envelope) and the theory of H-matrices, which has motivated new results as far as block and fractional pseudospectrum localizations are concerned, as well as some new upper bounds for the inverse of certain subclasses of H-matrices, both in the point-wise and block case, and the overall collective application of these results in the dynamical analysis of complex systems.

With the development of Low-altitude Low-Speed and Small-Target Aircraft (hereinafter referred to as LLS Aircraft), the number of dangerous accidents caused by them increases sharply. There is an urgent need to carry out research on the defense technology of LLS Aircraft. In the defense process of LLS Aircraft, the most important part is to recognize LLS Aircraft. Only on the basis of accurate recognition can we further achieve the accurate tracking, interception and disposal of different LLS Aircraft. Proposed in this paper, we study the LLS Aircraft recognition technology based on block-diagonal feature. We firstly extract the Histogram of Oriented Gradients (HOG) feature of LLS Aircraft images. Then the HOG feature is diagonalized by using low-rank recovery technology. The low-rank feature representation of LLS Aircraft is constructed by introducing a block-diagonal sparse regular term to increase the discrimination of LLS Aircraft feature. Based on the block-diagonal HOG feature, we use Support Vector Machine (SVM) to classify the LLS Aircraft, to enhance the accuracy of LLS Aircraft recognition.

In recent years, numerous studies have reported that high-aspect-ratio and rod-shaped nanoparticles, including carbon nanotubes and metallic nanowires, are promising materials for the next-generati...

Sparse-representation-based classification (SRC) has been widely studied and developed for various practical signal classification applications. However, the performance of a SRC-based method is degraded when both the training and test data are corrupted. To counteract this problem, we propose an approach that learns Representation with Block-Diagonal Structure (RBDS) for robust image recognition. To be more specific, we first introduce a regularization term that captures the block-diagonal structure of the target representation matrix of the training data. The resulting problem is then solved by an optimizer. Last, based on the learned representation, a simple yet effective linear classifier is used for the classification task. The experimental results obtained on several benchmarking datasets demonstrate the efficacy of the proposed RBDS method., accepted by Pattern Analysis and Applications

We study the problem of finding unitary submatrices of the $N \times N$ discrete Fourier transform matrix, in the context of interpolating a discrete bandlimited signal using an orthogonal basis. This problem is related to a diverse set of questions on idempotents on $\mathbb{Z}_N$ and tiling $\mathbb{Z}_N$. In this work, we establish a graph-theoretic approach and connections to the problem of finding maximum cliques. We identify the key properties of these graphs that make the interpolation problem tractable when $N$ is a prime power, and we identify the challenges in generalizing to arbitrary $N$. Finally, we investigate some connections between graph properties and the spectral-tile direction of the Fuglede conjecture., Submitted to IEEE Transactions on Information Theory

A special two-by-two block matrix form arises in many important applications. Extending earlier results it is shown that parameter modified versions of a very efficient preconditioner does not improve its rate of convergence. This holds also for iterative refinement methods corresponding to a few fixed steps of the Chebyshev accelerated method. The parameter version can improve the defect-correction method but the convergence of this method is slower than an iterative refinement method with an optimal parameter. The paper includes also a discussion of how one can save computer elapsed times by avoiding use of global inner products such as by use of a Chebyshev accelerated method instead of a Krylov subspace method. Since accurate and even sharp eigenvalue bounds are available, the Chebyshev iteration method converges as fast as the Krylov subspace method.

Given an n by n matrix A over the complex numbers and an invariant subspace L, this paper gives a straightforward formula to construct an n by n matrix N that commutes with A and has L equal to the kernel of N. For Q a matrix putting A into Jordan canonical form J = RAQ with R the inverse of Q, we get N = RM$ where the kernel of M is an invariant subspace for J with M commuting with J. In the formula M = P ZVW with V the inverse of a constructed matrix T and W the transpose of P, the matrices Z and T are m by m and P is an n by m row selection matrix. If L is a marked subspace, m = n and Z is an n by n block diagonal matrix, and if L is not a marked subspace, then m > n and Z is an m by m near-diagonal block matrix. Strikingly, each block of Z is a monomial of a finite-dimensional backward shift. Each possible form of Z is easily arranged in a lattice structure isomorphic to and thereby displaying the complete invariant subspace lattice L(A) for A., 12 pages with two illustrations of invariant subspace lattice diagrams

We develop and analyze a high-order outgoing radiation boundary condition for solving three-dimensional scattering problems by elongated obstacles. This Dirichlet to Neumann (DtN) condition is constructed using the classical method of separation of variables that allows to define the scattered field in a truncated domain. It reads as an infinite series which is truncated for numerical purposes. The radiation condition is implemented in a finite element framework represented by a large dense matrix. Fortunately, the dense matrix can be decomposed into a full block matrix which involves the degrees of freedom on the exterior boundary and a sparse finite element matrix. The inversion of the full block is avoided by using a Sherman-Morrison algorithm which reduces the memory usage drastically. Despite being of high-order, this method has only a low memory cost. Many applications such as sonar, radar or geophysical exploration involve exterior Helmholtz problems which raise the question of handling the unbounded propagation domain. One accurate approach consists in using boundary element methods (BEM), see Bendali & Fares (2008) and their references. The linear partial differential equation is reformulated as an integral equation which is set on the boundary of the scatterer. BEMs have thus the advantage of providing an exact reformulation of the exterior problem in a bounded region without introducing any kind of approximation before discretization. However , boundary element discretizations lead to dense matrices which increase both storage requirements and computational costs of the solution algorithm, especially in three dimensions. A popular alternative is the usage of volume finite element methods (FEM) Harari & Hughes (1992b) once the computational domain has been truncated. The truncation is performed by introducing an artificial boundary surrounding the scatterer which requires transforming the exterior problem into a mixed one corresponding to the initial volume formulation of the problem set in the bounded domain and coupled with a suitable boundary condition set on the external boundary. To get an accurate representation of the wave field into the bounded domain, the external boundary should not generate any reflection. This point is managed with †

Fundamental results and an efficient algorithm for constructing eigenvectors corresponding to non-zero eigenvalues of matrices with zero rows and/or columns are developed. The formulation is based on the relation between eigenvectors of such matrices and the eigenvectors of their submatrices after removing all zero rows and columns. While being easily implemented, the algorithm decreases the computation time needed for numerical eigenanalysis, and resolves potential numerical eigensolver instabilities.

Boolean control networks are a kind of discrete logical dynamical systems. They are recently attracting considerable interest as computational models for genetic and cellular networks. In this paper, we investigate the cascading state-space decomposition problem for Boolean control networks by nested method. Firstly, based on the semi-tensor product of matrices, we obtain some algebraic conditions for the cascading state-space decomposition. Secondly, the multi-layer nested block matrix is defined, and two necessary and sufficient conditions are put forward based on this kind of matrices. Besides, a method is given to design controllers. Finally, an example is given to display the effectiveness of the method provided in this paper.

Two difficulties continue to burden deep learning researchers and users: (1) neural networks are cumbersome tools, and (2) the activity of the fully connected (FC) layers remains mysterious. We make contributions to these two issues by considering a modified version of the FC layer we call a block diagonal inner product (BDIP) layer. These modified layers have weight matrices that are block diagonal, turning a single FC layer into a set of densely connected neuron groups; they can be achieved by either initializing a purely block diagonal weight matrix or by iteratively pruning off-diagonal block entries. This idea is a natural extension of group, or depthwise separable, convolutional layers. This method condenses network storage and speeds up the run time without significant adverse effect on the testing accuracy, addressing the first problem. Looking at the distribution of the weights through training when varying the number of blocks in a layer gives insight into the second problem. We observe that, even after thousands of training iterations, inner product layers have singular value distributions that resemble that of truly random matrices with iid entries and that each block in a BDIP layer behaves like a smaller copy. For network architectures differing only by the number of blocks in one inner product layer, the ratio of the variance of the weights remains approximately constant for thousands of iterations, that is, the relationship in structure is preserved in the parameter distribution.

We present a new construction of a symmetric arrow matrix from a particular spectral information: let λ(n) 1 be the minimal eigenvalue of the matrix and λj (j) , j = 1, 2, . . . , n the maximal eigenvalues of all leading principal submatrices of the matrix. We use such a procedure to construct a nonsymmetric arrow matrix from the same spectral information plus to an eigenvector x(n) = (x1, x2, . . . , xn), so that (x(n), λn (n)) is an eigenpair of the matrix. Moreover, our results generate an algorithmic procedure to compute a solution matrix.