Mathematical Foundation of Computer Science Laboratory

/ Yasuhiko Ikebe / Professor
/ Adam Kapralski / Associate Professor
/ Zbigniew Kokosinski / Assistant Professor

Prof. Ikebe joined the university on May 1st as a Professor and lab head. He was appointed to the Dean of the Department for Student Affairs on October 1st. He continued his research in two different areas: applied computation and bilingual hyperdictionary, both supported in part by three(3) national government grants, for each of which he served as principal investigator. Prof. Ikebe taught the mathematics to freshman, Mathematics I and II, their exercise sessions to go with them, and a part of Numerical Analysis with Prof. Y. Kikuchi's help.

Prof. Kapralski continued his research on the development of Depth Search Machines, their applications and other related topics. In particular, the parallel generation of combinatorial objects constitues the main focus of the Machines. He taught courses in logic design and accompanying exercise sessions.

Prof. Kokosinski research effort for the year was devoted to the design of parallel algorithms for generating and ranking/unranking combinatorial objects. He tought courses in computer literacy and exercise sessions for computer literacy, algorithms and data structures II and, partially, logic design (with Prof. Kapralski).

Profs. Ikebe, Kapralski and supervised respective students in their SCCP projects, the special extra-curricular student programs participated by all students of the university.

Refereed Journal Papers

1. Y. Ikebe, N. Asai, Y. Miyazaki, and D. Cai. The eigenvalue problem for infinite complex tridiagonal matrices with application. Linear Algebra and Its Applications, to appear.

   Given an infinite complex symmetric tridiagonal matrix T whose diagonal elements diverge to infinity and whose off-diagonal elements are bounded, the eigenvalue problem for T is posed in an appropriate space and the problem of approximating the eigenvalue of T by those of the truncated finite matrices is considered. An extremely accurate error estimate is obtained and proved. Applications to special functions of mathematical physics are given and significant new results are presented.

2. N. Asai, Y. Miyazaki, D. Cai, K. Hirasawa, and Y. Ikebe. A matrix method for the numerical solution of zj'n(z)+hjn(z)=0. The Transactions of The Institute of Electronics, Information and Communication Engineers, to appear.

   For the equation in the title, where H is a given nonzero complex constant, two types of problems are formulated and solved:(1) given n, generally complex, solve for z and (2) given nonzero complex z, solve for n. In each case, the problems is reformulated as an eigenvalue problem for an infinite tridiagonal matrix and is approximately solved by truncation. An extremely accurate error estimate is obtained in each case (In Japanese).

3. Kapralski A. Fast massively parallel algorithms for shortest path within planar figures. The Visual Computer, to appear, 1996.

   A problem of finding the shortest path between given terminal points s and t within a given planar figure F is considered. The approach contains basic methodology developed for any parallel or distributed system. The 2-D scene or the edge of F are represented in n-CCS (multiple coordinate system). The main operation of the proposed massively parallel or distributed algorithms is searching for pixels whose an individual coordinate is an extreme. Several algorithms for the shortest path are given, each one is to be applied in specific circuimstances depending on the exact machine model or on additional information we have concerning geometrical properties of the figure. If those algorithms are implemented in DSMs (depth search machines), then at most convenient circuimstances the shortest path can be produced in time O(1). The general recursive algorithm does not require any additional input information concerning the geometry of the figure F and it has complexity O(m); briefly speaking m is the number of "serpents" of a given figure and of the shortest path, simultaneously. More accurate specification of parameter m is given in the text. The given methodology can be also adopted for producing an approximate solution. Then the shortest path is approximated by polygonal lines but accuracy of the solution depends on the maximal number of applied processors and/or directions of the axes of the given n-CCS, while complexity of the adopted algorithms is the same as for the case of accurate solution.

1. Kokosinski Z. Algorithms for unranking combinations and their applications. In M. H. Hamza, editor, Proc. 7th IASTED Int. Conf. on Parallel and Distributed Computing and Systems, pages 216--224, Anaheim Calgary Zurich, October 1995. IASTED/ISMM, ACTA PRESS.

   In this paper new unranking algorithms are developed for a large class of choice functions representing various classes of combinatorial objects: combinations,complementary combinations, conjugate nondecreasing choice functions, ordered partitions. Presented algorithms differ with the type of lexicographic order they deal with and the method of binomial coefficient evaluation. Their correctness proofs provide a unified analysis of unranking techniques. All obtained algorithms are the best known within their classes. New unranking algorithms can be aplied in parallel systems for distribution of subtasks among processors and for parallel generartion of choice functions including their ordered subsets and random sequences.

2. Kokosinski Z. Unranking combinations in parallel, In Proc. 2nd CSREA Int. Conference Parallel and Distributed Processing, Techniques and Applications PDPTA'96, Sunnyvale, USA, to appear, August 1996.

   In this paper a parallel hardware-oriented algorithm is presented for unranking k out of n set subsets. The algorithm has O(k) time complexity and can be applied in specialized systems for parallel adaptive generation of the set of all combinations, its ordered subsets and any random sequences. This property enables fast distribution of subtasks among processors in parallel systems devoted for solving some classes of combinatorial problems. In particular the presented solution may be directly applied for programming hardware generators of combinations used in the associative computing.

3. Kokosinski Z. Generation of integer compositions on a linear array of processors. In In Proc. 2nd CSREA Int. Conference Parallel and Distributed Processing, Techniques and Applications, to appear, August 1996.

   In this paper two new parallel hardware-oriented algorithms are presented for generation of integer compositions. Both algorithms are optimal within their class. In oposition to existing solutions the algorithms do not use any tranformation from combinations, therefore they provide faster generation of integer compositons. Computations are accomplished in as weak model of computation as the linear array of processors model. Consequtive objects are generated in the decreasing lexicographic order. Ranking techniques for integer compositions are also described. An application of hardware integer composition generators in parallel combination generation is suggested.

1. Y. Ikebe. Handbook of Information Processing, pages 170--171. Ohm Publishing Company, 5.3.4 (Matrix Eigenvalue Problems), 1995.

   In Japanese.

1. T. Yamazaki, I. Fujishiro, and Y. Ikebe. Developing an english thesaurus database system with evolving semantics of words. In Proceedings of the Third (1995) Conference of Infomation and Knowledge Society, 1995.

1. Zbigniew Kokosinski. Algorithms for unranking combinations and other related choice functions. Technical Report, 95-1-006, February 27, The University of Aizu, Aizu-Wakamatsu, Japan, 1995.

2. Zbigniew Kokosinski. Unranking combinations in parallel. Technical Report, 95-1-023, May 31, 10pgs, The University of Aizu, Aizu-Wakamatsu, Japan, 1995.

3. Zbigniew Kokosinski. Generation of integer compositions on linear array of processors. Technical Report, 96-1-003, March 11, 11pgs, The University of Aizu, Aizu-Wakamatsu, Japan, 1996.

4. Adam Kapralski. Fast parallel algorithms for shortest path within planar figures. Technical Report, 95-1-027, June 8, 32pgs, The University of Aizu, Aizu-Wakamatsu, Japan, 1995.

5. Adam Kapralski. Parametric and structural models of planar shapes by usage of shortest paths, their measurements and hierarchy. Technical Report, 95-1-038, Nov. 16, 38pgs, The University of Aizu, Aizu-Wakamatsu, Japan, 1995.

Y. Ikebe. Grant: General(c), priority area(1), and international academic research (total amount 5.3 million yen), computer science the eigenvalue problem for infinite matrices and its application; a study on the construction of hyperdictionary; parallel algorithm for 3-d particle simulation using connection machines, 1995.

1. Zbigniew Kokosinski, 1995. PDCS'95 Conference, Session chair.

2. Zbigniew Kokosinski, 1995. IEEE-CS, Membership.

3. Zbigniew Kokosinski, 1995. IASTED, Membership.

4. Yasuhiko Ikebe, 1995. Prof. Ikebe has given several other talks and presentations, general and specialized, in addition to those cited above. He also helped his former graduate students at the University of Tsukuba in their preparation of thesis and dissertation. In particular, he served on a doctoral dissertation supervising committee for one of them.