Solving a linear multiperiod portfolio problem by interior-point methodology

In this report we formulate a linear multiperiod programming problem and show how it can be solved by a new interior point algorithm. The conditions of convergence and applicability of the algorithm of centers are explicitly connected to the multiperiod programming problem. For the former, effective application is supported by a set of simplifying conditions stated and proved in the text. For the latter, boundedness and nontriviality under real world conditions is demonstrated, allowing for its solution by the interior point algorithm. The use of a fast interior point algorithm is motivated by some empirical evidence from a Revised Simplex optimizer.     

Solving linear systems by methods based on a probabilistic interpretation

In this paper it is demonstrated how the probabilistic concept of a stopping time in a random process may be used to generate an iterative method for solving a system of linear equations. Actually all known iterative approximation methods for solving linear equations are generated by various choices of a stopping time e. g. the point and block Jacobi methods, the point and block Gauss-Seidel Methods and overrelaxation methods are covered. The probabilistic approach offers—in a natural way—the possibility of adapting the solution technique to the special structure of the problem. Moreover, posterior bounds for the solution are constructed, which lead to faster convergence of the approximations than with usual prior bounds.     

Solving fuzzy linear systems

In this paper, the main aim is to develop a method for solving an arbitrary general fuzzy linear system by using the embedding approach. Considering the existing and uniqueness of fuzzy solution to n × n linear fuzzy system is done. Numerical examples are presented to illustrate the proposed model.     

Solving EP singular linear systems

In this article, we deal with EP matrix and EP singular linear systems. We give some properties of EP matrix and its generalized inverse, analyze the solutions of EP systems and make some applications in Navier-Stokes equations.     

Solving linear finite element systems by normalized approximate matrix factorization semi-direct methods

New normalized Extended to the Limit sparse factorization procedures in algorithmic form are derived yielding direct and iterative methods for the solution of finite element or finite difference systems of irregular structure. The proposed factorization procedures are chosen as the basis to yield normalized systems on which the Conjugate Gradient and Chebychev methods are implicitly applied. The application of the derived normalized implicit semi-direct methods on a two-dimensional elliptic boundary-value problem is discussed and numerical results are given.     

Solving systems of sparse linear equations

We present in this work stable methods for solving sparse linear equations systems based on the LU factorizations and its updating when columns and rows of the system matrix are added, deleted or modified.     

Solving systems of large dense linear equations

Many mathematical models of physical phenomena lead to solving dense systems of linear equations. As the models are refined, the order of these problems increases, usually beyond the capacity of the computer to contain the problem in central memory. This paper reviews block Gaussian elimination, which can be used to solve these problems efficiently. An implementation that achieves the maximum sustainable computational rate on a wide range of computers is given. The question of how large of a problem is currently feasible is addressed.     

The interior-point method for linear programming

A robust, reliable, and efficient implementation of the primal-dual interior-point method for linear programs, which is based on three well-established optimization algorithms, is presented. The authors discuss the theoretical foundation for interior-point methods which consists of three crucial building blocks: Newton's method for solving nonlinear equations, Joseph Lagrange's methods for optimization with equality constraints, and Fiacco and McCormick's barrier method for optimization with inequality constraints. The construction of the primal-dual interior-point method using these methods is described. An implementation of the primal-dual interior-point method, its performance, and a comparison to other interior-point methods are also presented     

Solving systems of linear equations with Boolean variables

The paper presents a method to solve systems of linear equations with Boolean variables, which implements an enumeration strategy. Necessary and sufficient conditions for the existence of feasible plans are formalized. A formal procedure to analyze subsets of alternatives is described. The structure of an algorithm that possesses the property of completeness is presented. Special cases of systems of equations are examined. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 42–50, September–October 2006.     

Solving a modified consensus problem of linear multi-agent systems

A distributed protocol is proposed for a modified consensus problem of a network of agents that have the same continuous-time linear dynamics. Each agent estimates its own state using its output information and then sends the estimated state to its neighbor agents for the purpose of reaching a consensus. The modified consensus problem requires the group decision value to be a linear function of initial states and initial estimated states of all agents in the network, and the transformation matrix associated with this linear function not to be a zero matrix. It is proved that under the proposed control protocol, the modified consensus problem can be solved if and only if the system matrices of the agent’s dynamics are stabilizable and detectable, the input matrix is not a zero matrix, and the communication topology graph has a spanning tree. The proposed protocol can also be extended to multi-agent systems where agents are described by discrete-time linear dynamics. The corresponding necessary and sufficient conditions are provided as well.     

Solving systems of linear algebraic equations on array processors

Conclusion We have proposed a modification of the orthogonal Faddeev method [6] for solving various SLAE and also for inversion and pseudoinversion of matrices. The proposed version of the method relies on Householder and Jordan-Gauss methods and its computational complexity is approximately half that of [6]. This method, combined with the matrix-graph method [9] of formalized SPPC structure design, has been applied to synthesize a number of AP architectures that efficiently implement the proposed method. Goal-directed isomorphic and homeomorphic transformations of the LFG of the original algorithm (5) lead to a one-dimensional (linear) AP of fixed size, with minimum hardware and time costs and with minimized input-output channel width. The proposed algorithm (5) has been implemented using a 4-processor AP, with Motorola DSP96002 processors as PEs (Fig. 7). Application of the algorithm (5) to solve an SLAE with a coefficient matrixA withM=N=100 and one righthand side on this AP produced a load factor η=0.82; for inversion of the matrixA of the same size we achieved η=0.77. The sequence of transformations and the partitioning of a trapezoidal planaer LFG described in this article have been generalized to the case of other LA algorithms decribed by triangular planar LFGs and executed on linear APs. It is shown that the AP structures synthesized in this study execute all the above-listed algorithms no less efficiently than the modified Faddeev algorithm, provided their PEs are initially tuned to the execution of the corresponding operators. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 47–66, March–April, 1996.     

Solving linear equation systems on vector computers with maximum efficiency

A technique is presented for solving dense systems of linear equations by LU factorization with maximum performance on processors like FPS-120, FPS-5000 and X64 series, using FORTRAN with calls to elementary vector routines.

A rearrangement of the matrix elements is done in order to compute all the matrix-vector operations involved in the LU factorization with only stride-1 dot-product operations, which are executed at peak speed in the FPS processors.

Since only vector instructions are used, the algorithm is fully portable on all FPS 38/64 bit machines and in general on all vector computers with a similar memory structure.

The performance obtained on FPS-100 and FPS M64/60 (FPS-264) processors is reported: the asymptotic speed r_∞ is always the peak speed of the machine and the half performance length is N_1/2 = 238 for the FPS-100 and N_1/2 = 200 for the FPS M64/60. The N_1/2-values could be lowered by using the APAL Assembly Language to code some critical parts, losing however the code portability.     

Solving sparse linear systems of equations using the modified digraph approach

We propose two different algorithms which depend on the modified digraph approach for solving a sparse system of linear equations. The main feature of the algorithms is that the solution of a sparse system of linear equations can be expressed exactly if all the non-zero entries, including the right-hand side, are integers and if none of the products exceeds the size of the largest integer that can be represented in the arithmetic of the computer used. The implementation of the algorithms is tested on five problems. The results are compared with those obtained using an algorithm proposed earlier. It is shown that the efficiency with which a sparse system of linear equations can be analysed by a digital computer using the proposed modified digraph approach as a tool depends mainly on the efficiency with which semifactors and k-semifactors are generated. Finally, in our implementation of the proposed algorithms, the input sparse matrix is stored using a row-ordered list of a modified uncompressed storage scheme.     

Solving tridiagonal systems of linear equations on the IBM 3090 VF

Cyclic reduction, originally proposed by Hockney and Golub, is the most popular algorithm for solving tridiagonal linear systems on SIMD-type computers like CRAY-1 or CDC CYBER 205. That algorithm seems to be the adequate one for the IBM 3090 VF (uni-processor), too, although the overall expected speedup over Gaussian elimination, specialized for tridiagonal systems, is not as high as for the CRAY-1 or the CYBER 205. That is because the excellent scalar speed of the IBM 3090 makes its vector-to-scalar speed ratio relatively moderate.

The idea of the cyclic reduction algorithm can be generalized and modified in various directions. A polyalgorithm can be derived which takes into account much better the given architecture of the IBM 3090 VF than the ‘pure’ cyclic reduction algorithm as described for instance by Kershaw. This is mainly achieved by introducing more locality into the formulae. For large systems of equations the well-known cache problems are prevented.     

Solving large linear algebraic systems in the context of integrable non-abelian Laurent ODEs

The paper reports on a computer algebra program LSSS (Linear Selective Systems Solver) for solving linear algebraic systems with rational coefficients. The program is especially efficient for very large sparse systems that have a solution in which many variables take the value zero. The program is applied to the symmetry investigation of a non-abelian Laurent ODE introduced recently by M. Kontsevich. The computed symmetries confirmed that a Lax pair found for this system earlier generates all first integrals of degree at least up to 14.     

Solving large systems of linear ordinary differential equations on a vector computer

This paper is concerned with the development, analysis and implementation on a computer consisting of two vector processors of the arithmetic mean method for solving numerically large sparse sets of linear ordinary differential equations. This method has second-order accuracy in time and is stable.

The special class of differential equations that arise in solving the diffusion problem by the method of lines is considered. In this case, the proposed method has been tested on the CRAY X-MP/48 utilizing two CPUs. The numerical results are largely in keeping with the theory; a speedup factor of nearly two is obtained.     

Solving parametric fuzzy systems of linear equations by a nonlinear programming method

Linear systems of equations, with uncertainty on the parameters, play a major role in various problems in economics and finance. In this paper parametric fuzzy linear systems of the general form A ₁ x + b ₁ = A ₂ x + b ₂, with A ₁, A ₂, b ₁ and b ₂ matrices with fuzzy elements, are solved by means of a nonlinear programming method. The relation between this methodology and the algorithm proposed in Muzzioli and Reynaerts [(2006) Fuzzy Sets and Systems, in press] is highlighted. The methodology is finally applied to an economic and a financial problem.     

Chaotic methods for the papallel solution of linear systems

Chaotic synchronous and asynchronous schemes based on two-stage methods to solve nonsingular linear systems are presented. The convergence of these schemes is studied either when the chaotic parameters become sufficiently large or when the matrix in question is monotone. The results are illustrated by computational experiments on a shared memory multiprocessor vector computer.     

Tableau methods for analysis and design of linear systems

Certain classes of elementary operations on the system matrix of a linear system are defined, and then their use is illustrated for the calculation of canonical forms, the largest (A,B)-invariant and controllability subspaces in ker(C), transmission zeros, and minimal inverses. Questions of numerical accuracy are discussed. The results are directly codable as efficient numerical algorithms, and may be extended to the use of orthogonal transformations.     

The preconditioned variational methods for solving large linear systems

The implementation of the Preconditioned Conjugate Gradient method for the solution of large linear systems arising from the discretization of differential operators, requires the predetermination of only one iteration parameter. The numerical determination of the optimal value of this constant parameter, involve the spectral bounds of some matrices and can be obtained in O(N²) sine function evaluations, where 1/N is the discretization mesh size. It is shown that this parameter can be chosen in a stable manner in O(1) operations per iteration, if it is allowed to vary with the iteration index from information derived from the gradient parameters.