Complexity of factorization and GCD computation for linear ordinary differential operators

This paper presents an algorithm of polynomial complexity for finding greatest common (right) divisors of families of linear ordinary differential operators. An algorithm is presented for factorization of operators into the product of irreducible operators with complexity significantly better than that of previously known algorithms. Estimates are given for the coefficients of the expansion of the fundamental solution of the corresponding linear differential equation.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 176, pp. 68–103, 1989.     

Specific Features of Determining the Electrophysical Parameters of Variband CMT Structures Grown by Molecular-Beam Epitaxy

The effects of wide- and narrow- variband layers on the charge-carrier concentration and mobility in the MBE-grown epitaxial CMT structures measured by the Hall-effect method are studied by numerical simulation. The dependence of the relative difference between the experimentally obtained effective values of electrophysical parameters and those of an epitaxial coating on the variband-layer characteristics is discussed. An analysis of this dependence shows that the manner in which the broad-band and narrow-band layers affect the resulting parameters is inequivalent. The calculations suggest that the effect of the wide-band layer on the experimental electrophysical parameters can be neglected. In the case of the narrow variband layer, however, the difference between the electophysical parameters strongly depends on the variband-layer parameters and the concentrations of ionized donor and acceptor centers.     

Determination of a harmonic function with minimal gradient deviation

We find a function u(x, y) harmonic in the upper half-plane y>0 satisfying the conditions grad u(x₀,y₀) b|₂ min, . The solution of the problem is expressed in terms of the Poisson integral for the upper half-plane.Translated fromMatematicheskie Metody i Fiziko-Mekhanicheskie Polya, Issue 32, 1990, pp. 55–57.     

Photoelectron spectra and electronic structure of derivatives of imidazoline

We have obtained for the first time the photoelectron spectra (PES) of 20 diamagnetic and paramagnetic derivatives of imidazole. On the basis of calculations in the MNDO approximation, analysis of the vibrational structure, and comparisons in a series we have interpreted the bands in the range 7–11 eV. In the nitroxyl radicals of 3-imidazoline the highest occupied molecular orbital is the _NO ^* orbital, having also a contribution on the C⁴ atom. On introducing N-oxide groups there is a considerable rearrangement of the electronic structure of the radicals. In the PES of the nitroxyl radicals of 3-imidazoline-3-oxide there is multiplet splitting of the ionization band of the n_o·MO, amounting to 0.3–0.4 eV. Replacement of the methyl groups on the C² atom by methoxyl groups leads to an increase in the interactions of the unshared pairs of the O atoms of the nitronium and nitroxyl groups, while the same replacement on the C⁵ atoms leads to a considerable decrease in this interaction. When the substituent on the N¹ atom in derivatives of 3-imidazoline-3-oxide is varied the energy of ionization of the _C-NO MO decreases in the series: CH₃ < H OH < O < NO.Translated from Izvestiya Akademii Nauk SSSR, Seriya Khimicheskaya, No. 8, pp. 1769–1777, August, 1990.     

Algebraic complexity of the computation of a pair of bilinear forms

The problem mentioned in the titled reduces to the estimation of the rank of a collection of matrices. The rank of a collection of matrices A₁,...,A_e, denoted rk(A₁,...,A_e), is the least number of such one-dimensional matrices that their linear combinations will represent each matrix of the given collection. For an operator A on ⁿ there exists a space V and a diagonal operator B such that; we denote the minimal dimension of such spaces V by d(V)Theorem. For any matrix A we have the equality rk (E,A.)=n+d(A), where E is the identity matrix.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 47, pp. 159–163, 1974.     

Application of separability and independence notions for proving lower bounds of circuit complexity

This note consists of two independent parts. In the first part the concept of an (m,c)-system for a set of linear forms is introduced, and a lower bound is obtained for the algebraic complexity of the computation of (m,c)-systems on algebraic circuits of a special form. In the second part, the notion of an -independent set of boolean functions is introduced and a lower bound is obtained for a certain complexity measure for circuits of boolean functions computing -independent sets. As a corollary it is shown that the standard algorithm for multiplying matrices or polynomials may be realized by a circuit of boolean functions in a way that is optimal with respect to a selected complexity measure.Translated from Zapiski Nauchykh Seminarov Leningradskogo Otdeleniya Mathematicheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 60, pp. 38–48, 1976. Main results presented December 12, 1974 and May 29, 1975.The author would like to express his deep appreciation to A. O. Slisenko for his help.     

Relation between rank and multiplicative complexity of a bilinear form over a commutative Noetherian ring

The concept of multiplicative complexity of a bilinear form is introduced for a commutative Noetherian ring. Rings are described for which the multiplicative complexity coincides with the rank for all forms. It is shown that for regular rings of dimension 3 the multiplicative complexity can exceed the rank by an arbitrarily large number.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova, Vol. 86, pp. 66–81, 1979.