Search

With the rapid expansion of internet, the complex networks has become high-dimensional, sparse and redundant. Besides, the problem of link prediction in such networks has also obatined increasingly attention from different types of domains like information science, anthropology, sociology and computer sciences. It makes requirements for effective link prediction techniques to extract the most essential and relevant information for online users in internet. Therefore, this paper attempts to put forward a link prediction algorithm based on non-negative matrix factorization. In the algorithm, we reconstruct the correlation between different types of matrix through the projection of high-dimensional vector space to a low-dimensional one, and then use the similarity between the column vectors of the weight matrix as the scoring matrix. The experiment results demonstrate that the algorithm not only reduces data storage space but also effectively makes the improvements of the prediction performance during the process of sustaining a low time complexity. [ABSTRACT FROM AUTHOR]

Real nonsymmetric tridiagonal matrices arise in various applications. When one is asked to find the eigenvalues of such a matrix, the QR algorithm is used, but this destroys tridiagonal form by converting the matrix to Hessenberg form, resulting in increased storage requirements and numerical operations. The HR algorithm, based on the HR factorization of the matrix into a (Δ,Δ1)-orthogonal part H, where HTΔH = Δ1, and an upper triangular part R, solves this problem. In a result proved by Hongguo Xu, two steps of the LR algorithm are equivalent to one step of the QR algorithm for symmetric matrices. The first object of this paper is to use the HR algorithm to extend Hongguo Xu's result to the nonsymmetric case. Since an HR factorization does not always exist, so we also consider an extension to it called XHR factorization. We then prove a similar result about it. [ABSTRACT FROM AUTHOR]

The problem of linear equivalence for a general class of non-linear systems is examined throughout this paper. A relevant algorithm is developed based on a factorization procedure. This factorization is based on the star product, an operation corresponding to the cascade connection of systems. [ABSTRACT FROM PUBLISHER]

Abstract: Two kinds of decompositions of a -module are introduced in this article, a Loewy-decomposition and a primary decomposition. Algorithms are described which allow to construct decompositions for finite-dimensional -modules. Both decompositions rely on the concept of the -module of relative syzygies introduced in the paper. Furthermore an algorithm is described which tests whether two given -modules are isomorphic under the relevant type of transformations. [Copyright &y& Elsevier]

Polynomial expressions are frequently encountered in many application domains, particularly in signal processing and computer graphics. Conventional compiler techniques for redundancy elimination such as common subexpression elimination (CSE) are not suited for manipulating polynomial expressions, and designers often resort to hand optimizing these expressions. This paper leverages the algebraic techniques originally developed for multilevel logic synthesis to optimize polynomial expressions by factoring and eliminating common subexpressions. The proposed algorithm was tested on a set of benchmark polynomial expressions where savings of 26.7% in latency and 26.4% in energy consumption were observed for computing these expressions on the StrongARM SA1100 processor core. When these expressions were synthesized in custom hardware, average energy savings of 63.4% for minimum hardware constraints and 24.6% for medium hardware constraints over CSE were observed. [ABSTRACT FROM AUTHOR]

The paper continues the development of rank-factorization methods for solving certain algebraic problems for multi-parameter polynomial matrices and introduces a new rank factorization of a q-parameter polynomial m × n matrix F of full row rank (called the PG-q factorization) of the form F = PG, where $$P = \prod\limits_{k = 1}^{q - 1} {\prod\limits_{i = 1}^{n_k } {\nabla _i^{(k)} } } $$ is the greatest left divisor of F; Δ i is a regular (q-k)-parameter polynomial matrix the characteristic polynomial of which is a primitive polynomial over the ring of polynomials in q-k-1 variables, and G is a q-parameter polynomial matrix of rank m. The PG-q algorithm is suggested, and its applications to solving some problems of algebra are presented. Bibliography: 6 titles. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a fast algorithm which can be used to determine the triangular factorization of an inverse of a symmetric matrix of Loewner type by using O(n²) operations. [ABSTRACT FROM AUTHOR]

The article presents information on the properties of Graeco-Latin squares enumerated by mathematician Leonhard Euler. Euler suggested that a Graeco-Latin square of size n could never exist for any n of the form 4k +2, although he was not able to prove it. A Latin square is an n-by-n array of n distinct symbols in which each symbol appears exactly once in each row and column. On the other hand a Graeco-Latin square is an n-by-n array of ordered pairs from a set of n symbols such that in each row and each column of the array, each symbol appears exactly once in each coordinate. In one of his papers on Graeco-Latin squares, Euler used magic squares, which are closely related to Graeco-Latin squares. Magic squares were constructed by using Graeco-Latin squares of orders 3, 4 and 5. He showed that a Graeco-Latin square of order n can be converted into a magic square by the use of an algorithm. One can construct Graeco-Latin squares of every order n except those values for which the prime factorization of n contains only a single factor of 2.

In this paper we study plane conic geometry, particularly different representations of geometric constructions and relations in plane conic geometry, with Cayley and bracket algebras. We propose three powerful simplification techniques for bracket computation involving conic points, and an algorithm for rational Cayley factorization in conic geometry. The factorization algorithm is not a general one, but works for all the examples tried so far. We establish a series of elimination rules for various geometric constructions based on the idea of bracket-oriented representation and elimination, and an algorithm for optimal representation of the conclusion in theorem proving. These techniques can be used in any applications involving brackets and conics. In theorem proving, our algorithm based on these techniques can produce extremely short proofs for difficult theorems in conic geometry. [Copyright &y& Elsevier]

In a recent work, the author introduced a robust multilevel incomplete factorization algorithm using spanning trees of matrix graphs (Proceedings of the 1999 International Conference on Preconditioning Techniques for Large Sparse Matrix Problems in Industrial Applications, Hubert H. Humphrey Center, University of Minnesota, 1999, 251–257). Based on this idea linear and non-linear algebraic multilevel iteration (AMLI) methods are investigated in the present paper. In both cases, the preconditioner is constructed recursively from the coarsest to finer and finer levels. The considered W-cycles only need diagonal solvers on all levels and additionally evaluate a second-degree matrix polynomial (linear case), or, perform ν inner GCG-type iterations (non-linear case) on every other level. This involves the same type of preconditioner for the corresponding Schur complement. The non-linear variant has the additional benefit of being free from any method parameters to be estimated. Based on the same type of approximation property similar convergence rates are obtained for linear and non-linear AMLI, even for a very small number ν of inner iterations, e.g. ν =2,3. The presented methods are robust with respect to anisotropy and discontinuities in the coefficients of the PDEs and can also be applied to unstructured-grid problems. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We consider algebraic multilevel preconditioning methods based on the recursive use of a 2 × 2 block incomplete factorization procedure in which the Schur complement is approximated by a coarse grid matrix. As is well known, for discrete second-order elliptic PDEs, optimal convergence properties are proved for such basic two-level schemes under mild assumptions on the PDE coefficients, but their recursive use in a simple V-cycle algorithm does not generally lead to optimal order convergence. In the present paper, we analyse the combination of these techniques with a smoothing procedure much the same as the one used in standard multigrid algorithms, except that smoothing is not required on the finest grid. Theoretical results prove optimal convergence properties for the V-cycle under an assumption similar to the ‘approximation property’ of the classical multigrid convergence theory. On the other hand, numerical experiments made on both 2D and 3D problems show that the condition number is close to that of the two-level method. Further, the method appears robust in the presence of discontinuity and anisotropy, even when the material interfaces are not aligned with the coarse grid. Copyright © 1999 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]