Most tensor decomposition algorithms were developed for in-memory computation on a single machine. There are a few recent exceptions that were designed for parallel and distributed computation, but these cannot easily...
详细信息
ISBN:
(纸本)9781467369985
Most tensor decomposition algorithms were developed for in-memory computation on a single machine. There are a few recent exceptions that were designed for parallel and distributed computation, but these cannot easily incorporate practically important constraints, such as nonnegativity. A new constrained tensor factorization framework is proposed in this paper, building upon the Alternating Direction method of Multipliers (ADMoM). It is shown that this simplifies computations, bypassing the need to solve constrained optimization problems in each iteration, yielding algorithms that are naturally amenable to parallel implementation. The methodology is exemplified using nonnegativity as a baseline constraint, but the proposed framework can incorporate many other types of constraints. Numerical experiments are encouraging, indicating that ADMoM-based nonnegative tensor factorization (NTF) has high potential as an alternative to state-of-the-art approaches.
The longest common subsequence problem is to find a substring that is common to two given strings and is at least as long as any other such string. If m and n are the lengths of the two strings (m<2), we obtain O(l...
详细信息
The longest common subsequence problem is to find a substring that is common to two given strings and is at least as long as any other such string. If m and n are the lengths of the two strings (m<2), we obtain O(log m) time parallel algorithm with mn processors and an O(log/sup 2/ n) time optimal parallel algorithm. Serial complexity on the decision tree model is /spl Theta/(mn).
Data and control parallelism algorithms are described for a matrix method which detects and locates the presence of logic hazards in combinational logic circuits. Examples are given for illustration.
Data and control parallelism algorithms are described for a matrix method which detects and locates the presence of logic hazards in combinational logic circuits. Examples are given for illustration.
Each vertex of an undirected graph possesses a piece of information which must be sent to every other vertex. The method of communication is to send bounded size packets of messages from one vertex to another. We desc...
详细信息
Each vertex of an undirected graph possesses a piece of information which must be sent to every other vertex. The method of communication is to send bounded size packets of messages from one vertex to another. We describe parallel algorithms to accomplish the desired tasks for five prominent architectures. The algorithms are optimal, or nearly so, in every case.< >
Neural algorithmic reasoners are parallel processors. Teaching them sequential algorithms contradicts this nature, rendering a significant share of their computations redundant. parallel algorithms however may exploit...
详细信息
In motion rate control applications, it is faster and easier to solve the equations involved if the singular value decomposition (SVD) of the Jacobian matrix is first determined. A parallel SVD algorithm with minimum ...
详细信息
In motion rate control applications, it is faster and easier to solve the equations involved if the singular value decomposition (SVD) of the Jacobian matrix is first determined. A parallel SVD algorithm with minimum execution time is desired. One approach using Givens rotations lends itself to parallelization, reduces the iterative nature of the algorithm, and efficiently handles rectangular matrices. This research focuses on the minimization of the SVD execution time when using this approach. Specific issues addressed include considerations of data mapping, effects of the number of processors used on execution time, impacts of the interconnection network on performance, and trade-offs between modes of parallelism. Results are verified by experimental data collected on the PASM parallel machine prototype.< >
Two versions of a minimization algorithm for multiple-valued programmable logic arrays for shared and distributed memory multiprocessor systems are presented. Both algorithms exploit the considerable parallelism avail...
详细信息
Two versions of a minimization algorithm for multiple-valued programmable logic arrays for shared and distributed memory multiprocessor systems are presented. Both algorithms exploit the considerable parallelism available in the minimization problem. Discussed are communication, synchronization, and load balancing issues under the two machine models. Limited access and the cost of the required computation prevented running of the two parallel algorithms on the actual machines; however, it was possible to run parallel algorithms for a different, but very similar, problem that required less computation. These results indicate that excellent speedups, in some cases superlinear (i.e, more than the number of processors), can be obtained from parallel implementations of this logic minimization algorithm.< >
In 1961 Avizienis proposed a parallel algorithm for addition in base 10 with digit set A = {-6, -5, ..., 5, 6}. Such an algorithm performs addition in constant time, independently of the length of the representation o...
详细信息
In 1961 Avizienis proposed a parallel algorithm for addition in base 10 with digit set A = {-6, -5, ..., 5, 6}. Such an algorithm performs addition in constant time, independently of the length of the representation of the summands. In computer arithmetic parallel addition is used for speeding up multiplication and division algorithms. In this work we consider number systems where the base is a complex number β such that |β| > 1. We show that we can find a set of signed-digits on which addition is realizable by a parallel algorithm if and only if β is an algebraic number with no conjugate of modulus 1. We then address the question of the size of the digit set that permits parallel addition. We also investigate block parallel addition.
The authors present parallel solutions to the AMESCS (all maximal equally-spaced collinear subset) and AMRSS (all maximal regularly-spaced subset) problems and show how their solutions to the latter generalize to the ...
详细信息
The authors present parallel solutions to the AMESCS (all maximal equally-spaced collinear subset) and AMRSS (all maximal regularly-spaced subset) problems and show how their solutions to the latter generalize to the AMRSDLS (all maximal regularly-spaced D-dimensional lattice subsets) problem. Their algorithms differ significantly from the optimal sequential algorithms presented in A.B. Kahng and G. Robins (1991), which do not scale well to (massively) parallel machines. The optimality of the authors' Arbitrary CRCW PRAM (parallel random access machine) algorithms is open; however, the algorithms they present are within a logarithmic factor of optimal. Further, the algorithms are optimal for the mesh-connected computer.< >
暂无评论