A Parallel Network Equilibration Algorithm for a Class of Constrained Matrix Problems

Nagurney, Anna; Eydeland, Alexander
February 1992
Transportation Science;Feb92, Vol. 26 Issue 1, p59
Academic Journal
In this paper we propose a network equilibration algorithm for the solution of a class of constrained matrix problems with transportation-type constraints. The algorithm decomposes the problem into two series of supply and demand network equilibrium problems with special structure which can then be solved exactly and in parallel. The theoretical results obtained include the proof of convergence, the rate of convergence, and computational complexity analysis, and are obtained by interpreting the algorithm as a dual method. Computational results on datasets illustrate the theory and the efficiency of this approach.


Related Articles

  • Fast hybrid matrix multiplication algorithms. Jelfimova, L. D. // Cybernetics & Systems Analysis;Jul2010, Vol. 46 Issue 4, p563 

    New hybrid algorithms for matrix multiplication are proposed that have the lowest computational complexity in comparison with well-known matrix multiplication algorithms. Based on the proposed algorithms, efficient algorithms are developed for the basic operation $ D = C + \sum\limits_{l...

  • Models and algorithms for fair layout optimization problems. Fernandes Muritiba, Albert E.; Iori, Manuel; Martello, Silvano; Negreiros Gomes, Marcos J. // Annals of Operations Research;Sep2010, Vol. 179 Issue 1, p5 

    Given a non-convex two-dimensional area and identical rectangular stands, we consider the problem of placing the maximum number of stands in the area, by satisfying a number of operational constraints. We present linear programming models and show the total unimodularity of the matrices...

  • PERFORMANCE ANALYSIS OF STAP ALGORITHMS BASED ON FAST SPARSE RECOVERY TECHNIQUES. Yang, Z. C.; Liu, Z.; Li, X.; Nie, L. // Progress in Electromagnetics Research B;2012, Vol. 41, p251 

    In the field of space-time adaptive processing (STAP), spare recovery type STAP (SR-STAP) algorithms exploit formulation of the clutter estimation problem in terms of sparse representation of a small number of clutter positions among a much larger number of potential positions in the...

  • PERMUTING ELEMENTS WITHIN COLUMNS OF A MATRIX IN ORDER TO MINIMIZE MAXIMUM ROW SUM. Coffman, Jr., E. G.; Yannakakis, M. // Mathematics of Operations Research;Aug84, Vol. 9 Issue 3, p384 

    We study the problem of permuting the elements within columns of a given m x n matrix A so as to minimize its maximum row sum (sum of the elements in a row). We introduce and analyze an approximation algorithm of greedy type for this NP-complete problem. We prove that our algorithm produces...

  • New fast hybrid matrix multiplication algorithms. Jelfimova, L. // Cybernetics & Systems Analysis;Nov2011, Vol. 47 Issue 6, p881 

    New hybrid algorithms are proposed for multiplying ( n × n) matrices. They are based on Laderman's algorithm for multiplying (3 × 3)-matrices. As compared with well-known hybrid matrix multiplication algorithms, the new algorithms are characterized by the minimum computational...

  • An inversion algorithm for general tridiagonal matrix. Rui-sheng Ran; Ting-zhu Huang; Xing-ping Liu; Tong-xiang Gu // Applied Mathematics & Mechanics;Feb2009, Vol. 30 Issue 2, p247 

    An algorithm for the inverse of a general tridiagonal matrix is presented. For a tridiagonal matrix having the Doolittle factorization, an inversion algorithm is established. The algorithm is then generalized to deal with a general tridiagonal matrix without any restriction. Comparison with...

  • A Novel Recursive Multiplierless Algorithm for 2-D DCT. Ananthashayana, V. K.; Geetha, K. S. // World Academy of Science, Engineering & Technology;Aug2009, Issue 32, p518 

    In this paper, a recursive algorithm for the computation of 2-D DCT using Ramanujan Numbers is proposed. With this algorithm, the floating-point multiplication is completely eliminated and hence the multiplierless algorithm can be implemented using shifts and additions only. The orthogonality of...

  • Reflexive Incidence Matrix (RIM) Representation of Petri Nets. Das, Sajal K.; Agrawal, V. K.; Sarkar, Dilip; Patnaik, L. M.; Goel, P. S. // IEEE Transactions on Software Engineering;Jun87, Vol. 13 Issue 6, p643 

    Although incidence matrix representation has been used to analyze the Petri net based models of a system, it has the limitation that it does not preserve reflexive properties (i.e., the presence of self- loops) of Petri nets. But in many practical applications self-loops play very important...

  • DETERMINANTS AND INVERSES OF SKEW AND SKEW LEFT CIRCULANT MATRICES INVOLVING THE k-LUCAS NUMBERS IN COMMUNICATIONS - II. Xiao-Yu Jiang; Yun Gao; Zhao-Lin Jiang // Far East Journal of Mathematical Sciences;Jul2013, Vol. 78 Issue 1, p1 

    In this paper, we consider the skew circulant and skew left circulant matrices with the k-Lucas numbers in communications. First, we discuss the invertibility of the skew circulant matrix and present the determinant and the inverse matrix by constructing the transformation matrices. Furthermore,...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics