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.

Systemological Knowledge-based Technology for Solving Complete Ill-structured Problems

Original method and technology of systemological «Unit-Function-Object» analysis for solving complete ill-structured problems is proposed. The given visual grapho-analytical UFO technology for the fist time combines capabilities and advantages of the system and object approaches and can be used for business reengineering and for information systems design. UFO- technology procedures are formalized by pattern-theory methods and developed by embedding systemological conceptual classification models into the system-object analysis and software tools. Technology is based on natural classification and helps to investigate deep semantic regularities of subject domain and to take proper account of system-classes essential properties the most objectively. Systemological knowledge models are based on method which for the first time synthesizes system and classification analysis. It allows creating CASE-toolkit of a new generation for organizational modelling for companies’ sustainable development and competitive advantages providing.

Randomized Parallelization – a New Method for Solving Hard Combinatorial Problems

A new method for solving some hard combinatorial optimization problems is suggested, admitting a certain reformulation. Considering such a problem, several different similar problems are prepared which have the same set of solutions. They are solved on computer in parallel until one of them will be solved, and that solution is accepted. Notwithstanding the evident overhead, the whole run-time could be significantly reduced due to dispersion of velocities of combinatorial search in regarded cases. The efficiency of this approach is investigated on the concrete problem of finding short solutions of non-deterministic system of linear logical equations.

On the Mastering of Knowledge and Skills for Solving Mathematical Problems in the Context of the Relationship "Reflection–Synergy"

On the basis of topical investigations on the reflection in the mathematics education, in this article there are presented some contemporary ideas about refining the methodology of mastering knowledge and skills for solving mathematical problems. The thesis is developed that for the general logical and for some particular mathematical methods to become means of solving mathematical problems, first they need to be a purpose of the education.

A Method for Solving a Class of Multiple-Criteria Analysis Problems

AMS subject classification: 90C29.

Two Fundamental Problems Connected with AI

This paper is about two fundamental problems in the field of computer science. Solving these two problems is important because it has to do with the creation of Artificial Intelligence. In fact, these two problems are not very famous because they have not many applications outside the field of Artificial Intelligence. In this paper we will give a solution neither of the first nor of the second problem. Our goal will be to formulate these two problems and to give some ideas for their solution.

Genetic Algorithm Approach for Solving the Task Assignment Problem

This research was partially supported by the Serbian Ministry of Science and Ecology under project 144007. The authors are grateful to Ivana Ljubić for help in testing and to Vladimir Filipović for useful suggestions and comments.

Solving Fractional Diffusion-Wave Equations Using a New Iterative Method

Mathematics Subject Classification: 26A33, 31B10

A Metaheuristic Approach to Solving the Generalized Vertex Cover Problem

AMS Subj. Classification: 90C27, 05C85, 90C59

Solving Maximum Clique Problem for Protein Structure Similarity

Computing the similarity between two protein structures is a crucial task in molecular biology, and has been extensively investigated. Many protein structure comparison methods can be modeled as maximum weighted clique problems in specific k-partite graphs, referred here as alignment graphs. In this paper we present both a new integer programming formulation for solving such clique problems and a dedicated branch and bound algorithm for solving the maximum cardinality clique problem. Both approaches have been integrated in VAST, a software for aligning protein 3D structures largely used in the National Center for Biotechnology Information, an original clique solver which uses the well known Bron and Kerbosch algorithm (BK). Our computational results on real protein alignment instances show that our branch and bound algorithm is up to 116 times faster than BK.

Solving the Task Assignment Problem with a Variable Neighborhood Search

In this paper a variable neighborhood search (VNS) approach for the task assignment problem (TAP) is considered. An appropriate neighborhood scheme along with a shaking operator and local search procedure are constructed specifically for this problem. The computational results are presented for the instances from the literature, and compared to optimal solutions obtained by the CPLEX solver and heuristic solutions generated by the genetic algorithm. It can be seen that the proposed VNS approach reaches all optimal solutions in a quite short amount of computational time.

Direct and Inverse Spectral Problems for (2N + 1)-Diagonal, Complex, Symmetric, Non-Hermitian Matrices

2000 Mathematics Subject Classification: 42C05.

Notes on the Solution of Dynamic Optimization Problems with Explicit Controls in Discrete-Time Economic Models

Йордан Йорданов, Андрей Василев - В работата се изследват методи за решаването на задачи на оптималното управление в дискретно време с безкраен хоризонт и явни управления. Дадена е обосновка на една процедура за решаване на такива задачи, базирана на множители на Лагранж, коята често се употребява в икономическата литература. Извеждени са необходимите условия за оптималност на базата на уравнения на Белман и са приведени достатъчни условия за оптималност при допускания, които често се използват в икономиката.

Visualization of Problems’ Solution

Джурджица Такачи - В доклада се разглеждат дидактически подходи за решаване на задачи, упражнения и доказване на теореми с използване на динамичен софтуер, по-специално – с вече широко разпространената система GeoGebra. Въз основа на концепция-та на Пойа се анализира използването на GeoGebra като когнитивно средство за решаване на задачи и за обсъждане на техни възможни обобщения.

Monte Carlo Algorithms for Linear Problems

MSC Subject Classification: 65C05, 65U05.