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.

On some Modifications of the Nekrassov Method for Numerical Solution of Linear Systems of Equations

A modification of the Nekrassov method for finding a solution of a linear system of algebraic equations is given and a numerical example is shown.

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.

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.

Linear Classifiers Based on Binary Distributed Representations

Binary distributed representations of vector data (numerical, textual, visual) are investigated in classification tasks. A comparative analysis of results for various methods and tasks using artificial and real-world data is given.

Timed Transition Automata as Numerical Planning Domain

A general technique for transforming a timed finite state automaton into an equivalent automated planning domain based on a numerical parameter model is introduced. Timed transition automata have many applications in control systems and agents models; they are used to describe sequential processes, where actions are labelling by automaton transitions subject to temporal constraints. The language of timed words accepted by a timed automaton, the possible sequences of system or agent behaviour, can be described in term of an appropriate planning domain encapsulating the timed actions patterns and constraints. The time words recognition problem is then posed as a planning problem where the goal is to reach a final state by a sequence of actions, which corresponds to the timed symbols labeling the automaton transitions. The transformation is proved to be correct and complete and it is space/time linear on the automaton size. Experimental results shows that the performance of the planning domain obtained by transformation is scalable for real world applications. A major advantage of the planning based approach, beside of the solving the parsing problem, is to represent in a single automated reasoning framework problems of plan recognitions, plan synthesis and plan optimisation.

Numerical Approximation of a Fractional-In-Space Diffusion Equation, I

2000 Mathematics Subject Classification: 26A33 (primary), 35S15 (secondary)

Numerical Approximation of a Fractional-In-Space Diffusion Equation (II) – with Nonhomogeneous Boundary Conditions

2000 Mathematics Subject Classification: 26A33 (primary), 35S15

Interior Boundaries for Degenerate Elliptic Equations of Second Order Some Theory and Numerical Observations

2010 Mathematics Subject Classification: Primary 35J70; Secondary 35J15, 35D05.

A Refinement of some Overrelaxation Algorithms for Solving a System of Linear Equations

In this paper we propose a refinement of some successive overrelaxation methods based on the reverse Gauss–Seidel method for solving a system of linear equations Ax = b by the decomposition A = Tm − Em − Fm, where Tm is a banded matrix of bandwidth 2m + 1. We study the convergence of the methods and give software implementation of algorithms in Mathematica package with numerical examples. ACM Computing Classification System (1998): G.1.3.