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.

Teaching University-Level Mathematics Using Mathematica

This paper considers the use of the computer algebra system Mathematica for teaching university-level mathematics subjects. Outlined are basic Mathematica concepts, connected with different mathematics areas: algebra, linear algebra, geometry, calculus and analysis, complex functions, numerical analysis and scientific computing, probability and statistics. The course “Information technologies in mathematics”, which involves the use of Mathematica, is also presented - discussed are the syllabus, aims, approaches and outcomes.

Stochastic Arithmetic Theory and Experiments

Stochastic arithmetic has been developed as a model for exact computing with imprecise data. Stochastic arithmetic provides confidence intervals for the numerical results and can be implemented in any existing numerical software by redefining types of the variables and overloading the operators on them. Here some properties of stochastic arithmetic are further investigated and applied to the computation of inner products and the solution to linear systems. Several numerical experiments are performed showing the efficiency of the proposed approach.

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

The Automorphism Group of the Free Algebra of Rank Two

The theorem of Czerniakiewicz and Makar-Limanov, that all the automorphisms of a free algebra of rank two are tame is proved here by showing that the group of these automorphisms is the free product of two groups (amalgamating their intersection), the group of all affine automorphisms and the group of all triangular automorphisms. The method consists in finding a bipolar structure. As a consequence every finite subgroup of automorphisms (in characteristic zero) is shown to be conjugate to a group of linear automorphisms.

Operational Methods in the Environment of a Computer Algebra System

This article presents the principal results of the doctoral thesis “Direct Operational Methods in the Environment of a Computer Algebra System” by Margarita Spiridonova (Institute of mathematics and Informatics, BAS), successfully defended before the Specialised Academic Council for Informatics and Mathematical Modelling on 23 March, 2009.