Quasi-Monte Carlo Methods for some Linear Algebra Problems. Convergence and Complexity

We present quasi-Monte Carlo analogs of Monte Carlo methods for some linear algebra problems: solving systems of linear equations, computing extreme eigenvalues, and matrix inversion. Reformulating the problems as solving integral equations with a special kernels and domains permits us to analyze the quasi-Monte Carlo methods with bounds from numerical integration. Standard Monte Carlo methods for integration provide a convergence rate of O(N^(−1/2)) using N samples. Quasi-Monte Carlo methods use quasirandom sequences with the resulting convergence rate for numerical integration as good as O((logN)^k)N^(−1)). We have shown theoretically and through numerical tests that the use of quasirandom sequences improves both the magnitude of the error and the convergence rate of the considered Monte Carlo methods. We also analyze the complexity of considered quasi-Monte Carlo algorithms and compare them to the complexity of the analogous Monte Carlo and deterministic algorithms.

MultiDecision-2: A Multicriteria Decision Support System

The paper presents a multicriteria decision support system, called MultiDecision-2, which consists of two independent parts - MKA-2 subsystem and MKO-2 subsystem. MultiDecision-2 software system supports the decision makers (DMs) in the solving process of different problems of multicriteria analysis and linear (continues and integer) problems of multicriteria optimization. The two subsystems MKA-2 and MKO-2 of of MultiDecision-2 are briefly described in the paper in the terms of the class of the problems being solved, the system structure, the operation with the interface modules for input data entry and the information about DM’s local preferences, as well as the operation with the interface modules for visualization of the current and final solutions.

On the Error-Correcting Performance of some Binary and Ternary Linear Codes

In this work, we determine the coset weight spectra of all binary cyclic codes of lengths up to 33, ternary cyclic and negacyclic codes of lengths up to 20 and of some binary linear codes of lengths up to 33 which are distance-optimal, by using some of the algebraic properties of the codes and a computer assisted search. Having these weight spectra the monotony of the function of the undetected error probability after t-error correction P(t)ue (C,p) could be checked with any precision for a linear time. We have used a programm written in Maple to check the monotony of P(t)ue (C,p) for the investigated codes for a finite set of points of p € [0, p/(q-1)] and in this way to determine which of them are not proper.

Computing and Visualizing Solution Sets of Interval Linear Systems

The paper has been presented at the 12th International Conference on Applications of Computer Algebra, Varna, Bulgaria, June, 2006

CAPS in Z(2,n)

We consider point sets in (Z^2,n) where no three points are on a line – also called caps or arcs. For the determination of caps with maximum cardinality and complete caps with minimum cardinality we provide integer linear programming formulations and identify some values for small n.

Necessary and Sufficient Conditions for the Extendability of Ternary Linear Codes

We give the necessary and sufficient conditions for the extendability of ternary linear codes of dimension k ≥ 5 with minimum distance d ≡ 1 or 2 (mod 3) from a geometrical point of view.

Involutivity and Symple Waves in R^2

A strictly hyperbolic quasi-linear 2×2 system in two independent variables with C2 coefficients is considered. The existence of a simple wave solution in the sense that the solution is a 2-dimensional vector-valued function of the so called Riemann invariant is discussed. It is shown, through a purely geometrical approach, that there always exists simple wave solution for the general system when the coefficients are arbitrary C^2 functions depending on both, dependent and independent variables.