|
Every solution is either trivial or false.
| |
| -- Zhijing George Mou. |
Ordered by date of original research or of publication.
C. F. Gauss, "Nachlass, Theoria Interpolationis Methodo Nova
Tractata," in Carl Friedrich Gauss Werke, Band 3, Koniglichen
Gesellschaft der Wissenschaften: Gottingen, pp. 265-330, 1866.
H. BURKHARDT,"Trigonometrische Interpolation," in Chapter 9, Encyklopiidie der
Mathematischen Wissenschaften, vol. 2, part 1, 1st half, 1899-1916.
H. BURKHARDT,"Trigonometrische Reihenund Integrale(bis etwa
1850)," in Chapter 12, Encyklopiidie der Mathematischen
Wissenschaften,vol. 2, part 1, 2nd half, 1904-1916.
J. W. COOLEY & J. W. TUKEY, "An Algorithm for the Machine
Calculation of Complex Fourier Series," Math. Comput., Vol. 19,
no. 2, pp. 297-301, Reprinted in Digital
Signal Processing, ed. Larry R. RABINER & C. M. RADER, pp. 223-227, New
York: IEEE Press, 1972, Apr. 1965.
Alan Perlis, The Synthesis of Algorithmic Systems, The 1st Turing
Lecture. (ACM V 14 No 1, 1967).(cached copy here)
Donald Fraser. Array permutation by index-digit
permutation. Journal of ACM, 23(2):298—309, April 1976.
The 1977
Turing Lecture. Can Programming Be Liberated from the von
Neumann Style? A Functional Style and Its Algebra of Programs, by
John Backus, IBM Research Laboratory, San Jose CA
MICHAEL T. HEIDEMAN, DON H. JOHNSON, C. SIDNEY BURRUS "Gauss and
the History of the Fast Fourier Transform", 1985. Rice U
Eng. Dept.
cached copy here.
Z. G. Mou and P. Hudak. An algebraic model for divide-and-conquer
algorithms and its parallelism. The Journal of Supercomputiug,
2(3):257-278, November 1988.
cached copy.
The design and analysis of parallel algorithms / by Selim G. Akl.
1989, Prentice Hall textbook,
cached copy here.
This was the state of the art before George Mou.
Zhijing George Mou, A Formal Model for Divide-and-Conquer and Its
Parallel Realization, May 1990, Research Report
YALEU/DCS/RR-795. (Yale
PhD Thesis)
Z. G. Mou. Divacon: A parallel language for scientific computing
based on divide-and-conquer. In Proceedings of the Third
Symposium on the Frontiers of Massively Parallel Computation,
pages 451-461. IEEE, October 1990. Link.
Abstract:
An overview of the language, covering Divacon primitives and
simple programming constructs that are referred to as
functional forms, is given. Two divide-and-conquer programming
constructs are discussed. Divacon style programming is
demonstrated for a number of scientific applications. Some
interesting equivalences and transformations between Divacon
programs are examined. Implementation and performance are
briefly considered.
Z. G. Mou and M. Goodman, "A Comparison of Communication Costs
for Three Parallel Programming Paradigms on Hypercube and Mesh
Architectures". Proc. 5th SIAM Conf. on Parallel Processing
p491-500, held in Houston TX March 1991.
ACM
link here.
B. Carpentieri, Z. G. Mou, Compile-time transformations and
optimization of parallel Divide-and-Conquer algorithms Published in
SIGP 1 October 1991. ACM SIGPLAN Notices.
Link.
Abstract:
The goal is to make Divide-and-Conquer algorithms suitable
for implementation on hypercube-like parallel architectures,
such as the Connection Machine, even if the original
algorithm implies a division function that is not the
left-right division and/or communication pattern that cannot
be implemented by direct-neighbor communication
Marc Goodman, Z. G. Mou, DC Transpose: a method for reducing
communication in divide-and-conquer algorithms on mesh-based
computers. Published in Proceedings of the Third IEEE Symposium
on Parallel and Distributed Processing 2 December 1991.
Abstract:
The paper introduces the notion of a DC Transpose, which is a
remapping of data on a mesh, using a global routing mechanism
such as the global router on the Mas-Par MP-1, to solve
divide-and-conquer algorithms.
Xiaojing Wang, Z. G. Mou. "A divide-and-conquer method of
solving tridiagonal systems on hypercube massively parallel
computers" Proceedings of the Third IEEE Symposium on Parallel
and Distributed Processing. 2 December 1991. Link here.
Abstract: The authors present a new parallel algorithm,
based on the divide-and-conquer (DC) strategy, for solving
tridiagonal systems, and show that for the binary hypercube
architecture, the communication complexity of their DC method
is the lowest among all, and therefore the most
efficient tridiagonal solver for communication-expensive
massively parallel hypercube computers.
Z. G. Mou, C. Constantinescu, and T. Hickey. Divide-and-conquer
on a 3-dimensional mesh. In Proceedings of the European Workshops
on Parallel Computing, pages 344-355, Barcelona, Spain, March
1992.
Z.G.Mou, Cornel Constantinescu, and T. Hickey. Optimal mappings
of divide-and-conquer algorithms to mesh connected parallel
architectures. In Proceedings of International Computer
Symposium, pages 273-284, Taiwan, December 1992.
Z. G. Mou, Xiaojing Wang, T. Hickey. Divide-and-Conquer
Algorithms with Recursive Broadcast Communication on
Reconfigurable Arbitrary Dimensional Mesh. Published in SIAM
Conference on Parallel Processing for Scientific Computing. 1993.
Z. George Mou and Xiaojing Wang, Optimal Mappings of m
Dimensional FFT Communication to k Dimensional Mesh for Arbitrary
m and k. pp 104-119. in PARLE '93, Parallel Architectures and
Languages Europe, Lecture Notes in Computer Science #694,
Springer-Verlag. 5th International PARLE Conference, Munich,
Germany, June 1993 Proceedings.
cached copy here.
Z.G. Mou. A Divide-and-Conquer Parallel Algorithm for Banded
Linear Systems. PP, 1995.
Jayadev Misra, Powerlist: A Structure for Parallel Recursion. ACM
Transactions. on Programming Languages and Systems, Vol 16, N. 6
November 1994, Pages 1737-1767.
Z.G. Mou. "Spectrum analysis and min-cut transformation
of communication networks in parallel computers" Published in:
Proceedings Frontiers '95. The Fifth Symposium on the Frontiers
of Massively Parallel Computation (IEEE) Conference in McLean,
VA, USA on 6-9 February 1995. Link here.
Abstract: We present a formal model for the
analysis of communication networks in parallel computers. Unlike
most others, our model focuses on the transmission delays as
opposed to the propagation delays of communication patterns. The
model allows all symmetric communication networks to be examined
by their spectrums and characterized by their transmission
dimensions. A min-cut transformation is introduced as a tool for
the spectrum analysis, which reduces any symmetric network to the
same canonical form. Parallel architectures with different
topologies can then be easily compared and
evaluated.
Z. G. Mou. The elements, structure, and taxonomy of
divide-and-conquer. In Theory and Practice of Higher-Order
Parallel Programming, Dagstul Seminar Report 169, pages 13–14,
February 1997.
Jeffrey Yepez, Guy P. Seeley, and George Mou. Lattice-gas
automata on parallel architectures. In Proceedings of
International Symposium on Parallel Computation, pages 522–525,
1993. Beijing, China. (For review on lattice gas automata see
The Classical Lattice-Gas Method by Jeffrey Yepez 1999,
DTIC/ADA455835.pdf).
Mou, Z.G. (1999). Recursive individually distributed object. In: Rolim, J., et al. Parallel and Distributed Processing. IPPS 1999. Lecture Notes in Computer Science, vol 1586. Springer, Berlin, Heidelberg . https://doi.org/10.1007/BFb0097888. Paper presented at IPPS/SPDP Workshops
12 April 1999
TLDR:
This paper proposes an alternative model called Individually
Distributed Object (IDO) which allows a single large object to
be distributed over a network, thus providing a high level
interface for the exploitation of parallelism inside the
computation of each object which was left out of the
distributed objects model.
Abstract: Distributed Objects (DO) as defined by OMG’s
CORBA architecture provide a model for object-oriented
parallel distributed computing. The parallelism in this model
however is limited in that the distribution refers to the
mappings of different objects to different hosts, and not to
the distribution of any individual object. We propose in this
paper an alternative model called Individually Distributed
Object (IDO) which allows a single large object to be
distributed over a network, thus providing a high level
interface for the exploitation of parallelism inside the
computation of each object which was left out of the
distributed objects model. Moreover, we propose a set of
functionally orthogonal operations for the objects which allow
the objects to be recursively divided, combined, and
communicate over recursively divided address
space. Programming by divide-and-conquer is therefore
effectively supported under this framework. The Recursive
Individually Distributed Object (RIDO) has been adopted as the
primary parallel programming model in the Brokered Objects for
Ragged-network Gigaflops (BORG) project at the Applied Physics
Laboratory of Johns Hopkins University, and applied to
large-scale real-world problems.
Google's
MapReduce paper MapReduce: Simplified Data Processing on
Large Clusters Jeffrey Dean and Sanjay Ghemawat, 2004.
Zhijing G. Mou, Hai Liu, Paul Hudak, Compress-and-Conquer for
Optimal Multicore Computing, In Proceedings of the POPL 2010
Workshop on Declarative Aspects of Multicore Programming, DAMP
2010, Madrid, Spain, January 19, 2010.
ACM link here,
ResearchGate link here,
cached copy here.
Abstract:
The CC paradigm is implemented in Haskell as a modular,
higher-order function, compiled into low-level Haskell threads
that run on a multicore machine, and performance benchmarks
confirm the theoretical analysis.
Z. George Mou, Black-White Array: A New Data Structure for
Dynamic Data Sets. April 2020, arXiv preprint here. cached
copy here.
Orian Leitersdorf, Yahav Boneh, Gonen Gazit, Ronny Ronen, Shahar
Kvatinsky, FourierPIM: High-Throughput In-Memory Fast Fourier
Transform and Polynomial Multiplication Viterbi Faculty of
Electrical and Computer Engineering, Technion – Israel Institute
of Technology, Haifa, 3200003, Israel. ArXiv 2304.02336v1
[cs.AR] 5 Apr 2023.
Patent US20230351547A1, Methods and control systems that use
dimensional-transform-based three-dimensional searching and voxel
mapping. Published 02-November-2023.
|
