PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 18

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  graph grammar
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available Hypergraph grammar based multi-thread multi-frontal direct solver with Galois scheduler
Jopek Konrad, Paszyński Maciej, Paszyńska Anna, Hassan Muhammad Amber, Pingali Keshav
Computer Science
|
2019
|
Vol. 20 (1)
27--55
EN
In this paper, we analyze two-dimensional grids with point and edge singularities in order to develop an eficient parallel hypergraph grammar-based multi- frontal direct solver algorithm. We express these grids by a hypergraph. For these meshes, we define a sequence of hypergraph grammar productions expressing the construction of frontal matrices, eliminating fully assembled nodes, merging the resulting Schur complements, and repeating the process of elimination and merging until a single frontal matrix remains. The dependency relationship between hypergraph grammar productions is analyzed, and a dependency graph is plotted (which is equivalent to the elimination tree of a multi- frontal solver algorithm). We utilize a classical multi-frontal solver algorithm; the hypergraph grammar productions allow us to construct an eficient elimination tree based on the graph representation of the computational mesh (not the global matrix itself). The hypergraph grammar productions are assigned to nodes on a dependency graph, and they are implemented as tasks in the GALOIS parallel environment and scheduled according to the developed dependency graph over the shared memory parallel machine. We show that our hypergraph grammar-based solver outperforms the parallel MUMPS solver.
2
Content available Interpreted Graphs and ETPR(k) Graph Grammar Parsing for Syntactic Pattern Recognition
Flasiński M.
Machine Graphics and Vision
|
2018
|
Vol. 27, No. 1/4
3--19
EN
Further results of research into graph grammar parsing for syntactic pattern recognition (Pattern Recognit. 21:623-629, 1988; 23:765-774, 1990; 24:1223-1224, 1991; 26:1-16, 1993; 43:249-2264, 2010; Comput. Vision Graph. Image Process. 47:1-21, 1989; Fundam. Inform. 80:379-413, 2007; Theoret. Comp. Sci. 201:189-231, 1998) are presented in the paper. The notion of interpreted graphs based on Tarski's model theory is introduced. The bottom-up parsing algorithm for ETPR(k) graph grammars is defined.
3
Content available Generative power of reduction-based parsable ETPR(k) graph grammars for syntactic pattern recognition
Flasiński M.
Journal of Automation Mobile Robotics and Intelligent Systems
|
2018
|
Vol. 12, No. 2
61--81
EN
Further results of research into parsable graph grammars used for syntactic pattern recognition (Pattern Recognition: 21, 623-629 (1988); 23, 765-774 (1990); 24, 12-23 (1991); 26, 1-16 (1993); 43, 2249-2264 (2010), Comput. Vision Graph. Image Process. 47, 1-21 (1989), Computer-Aided Design 27, 403-433 (1995), Theoret. Comp. Sci. 201, 189-231 (1998), Pattern Analysis Applications bf 17, 465-480 (2014)) are presented in the paper. The generative power of reduction-based parsable ETPR(k) graph grammars is investigated. The analogy between the triad of CF - LL(k) - LR(k) string languages and the triad of NLC - ETPL(k) - ETPR(k) graph languages is discussed.
4
Content available remote Using the system of graph grammar for generation of quasi optimal element partition trees in two dimensions
Paszyńska A., Świderska I., Woźniak M., Jopek K., Paszyński M., Grabska E., Lenhart A., Nguyen D., Pingali K.
Computer Methods in Materials Science
|
2016
|
Vol. 16, No. 3
143--155
EN
The paper presents a graph grammar based approach for h-adaptive finite element method and multi-frontal solver algorithm. The multi-frontal solver is used for solving systems of linear equations created by finite element method. The multi-frontal solver is controlled by so-called ordering. The quality of ordering influences hardly the solver effectiveness. In our approach, the finite element mesh is represented by means of a hypergraph and corresponding element partition tree. The finite element operations like mesh generation or h-adaptation are modelled by graph grammar production. Additionally graph grammar productions have corresponding productions for the construction of the element partition tree. The element partition trees are transformed into the ordering that controlls execution of the solver algorithm. We show that the ordering resulting from our element partititon tree results in better performance of the parallel solver than the state of the art nested-dissection ordering available through MUMPS interface on the class of grids refined towards singularities.
PL
W artykule tym prezentujemy gramatykę grafową do modelowania algorytmów h adaptacyjnej metody elementów skończonych oraz solwera wielofrontalncgo. Solwer wielofronatlny używany jest do rozwiązania układu równań liniowych stworzonych przez metodę elementów skończonych. Solwer ten kontrolowany jest przez tak zwany porządek eliminacji. Jakość porządku eliminacji wpływa na efektywność solwera wielofrontalnego. W naszym podejściu siatka metody elementów skończonych reprezentowana jest przez hipergraf oraz związane z nim drzewo podziałów siatki. Operacje na elementach skończonych takie jak generacja siatki oraz h adaptacja modelowane są przez produkcję gramatyki grafowej. Dodatkowo, gramatyka grafowa posiada powiązane produkcje do generacji drzewa podziałów siatki. Drzewo podziałów siatki z kolei transformowane jest w porządek eliminacji, który kontroluje wykonanie algorytmu solwera. Pokazujemy że porządek eliminacji uzyskany na podstawie naszego drzewa podziałów siatki daje lepszą wydajność algorytmu solwera równoległego w porównaniu z klasycznym porządkiem nested- disseetions dostępnym w solwerze MUMPS, dla klas siatek adaptowalnych do lokalnych osobliwości.
5
Content available Grammar based multi-frontal solver for isogeometric analysis in 1d
Kuźnik K., Paszyński M, Calo V.
Computer Science
|
2013
|
Vol. 14 (4)
589--613
EN
In this paper, we present a multi-frontal direct solver for one-dimensional iso-geometric finite element method. The solver implementation is based on the graph grammar (GG) model. The GG model allows us to express the entire solver algorithm, including generation of frontal matrices, merging, and eliminations as a set of basic undividable tasks called graph grammar productions. Having the solver algorithm expressed as GG productions, we can find the partial order of execution and create a dependency graph, allowing for scheduling of tasks into shared memory parallel machine. We focus on the implementation of the solver with NVIDIA CUDA on the graphic processing unit (GPU). The solver has been tested for linear, quadratic, cubic, and higher-order B-splines, resulting in logarithmic scalability.
6
Content available remote Graph grammar for three dimensional multi physics adaptive finite element method simulations
Paszyńska A., Paszyński M
Computer Methods in Materials Science
|
2013
|
Vol. 13, No. 1
9--15
EN
In this paper we present an application of graph grammar for modelling a three dimensional hp adaptive finite element method for multi-physics simulations. The graph grammar model involves the process of generation of the mesh with tetrahedral finite elements, the process of mesh adaptation by means of h refinement as well as interfacing with the multi-frontal solver algorithm by translating the finite elements into a sequence of frontal matrices, being an input for the multi-frontal solver algorithm. The paper is concluded with numerical results concerning an advanced multi-physics problems, the propagation of an acoustic waves over the model of the human head.
PL
W artykule tym przedstawiamy gramatykę grafową do modelowania adaptacyjnej metody elementów skończonych służącej do wykonywania trójwymiarowych symulacji problemów wielo-fizycznych. W szczególności model gramatyki grafowej obejmuje proces generacji siatki obliczeniowej zbudowanej z elementów czworościennych, proces zagęszczania siatki obliczeniowej za pomocą mechanizmu h adaptacji, a także interfejs do solwera wielo-frontalnego uzyskany poprzez generowanie ciągu macierzy frontalnych dla poszczególnych elementów skończonych. Artykuł podsumowują przykładowe wyniki symulacji dotyczące zagadnienia propagacji fal akustycznych na modelu głowy ludzkiej.
7
Content available remote A Graph GrammarModel of the hp Adaptive Three Dimensional Finite Element Method. Part I
Paszyńska A., Grabska E., Paszyński M.
Fundamenta Informaticae
|
2012
|
Vol. 114, nr 2
149-182
EN
The first part of our paper presents a composite programmable graph grammar model for the self-adaptive two dimensional hp Finite Element Method algorithms (2D hp-FEM) with mixed triangular and rectangular finite elements. The two dimensional model is a starting point for the three dimensional model of self-adaptive hp-FEM presented in the second part of this paper. A computational mesh is represented by a composite graph. The operations performed over the mesh are expressed by the graph grammar rules. The three dimensional model is based on the extension of the two dimensional model with rectangular finite elements. In the second part of this paper, we conclude the presentation with numerical examples concerning the generation of the optimal mesh for simulation of the Step-and-Flash Imprint Lithography (SFIL).
8
Content available remote A Graph GrammarModel of the hp Adaptive Three Dimensional Finite Element Method. Part II
Paszyńska A., Grabska E., Paszyński M.
Fundamenta Informaticae
|
2012
|
Vol. 114, nr 2
183-201
EN
This paper presents a composite programmable graph grammar model of the three dimensional self-adaptive hp Finite Element Method (hp-FEM) algorithms. The computational mesh composed of hexahedral finite elements is represented by a composite graph. The operations performed over the mesh are expressed by composite graph grammar productions. The three dimensional model is based on the extension of the two dimensional model for rectangular finite elements. This paper is concluded with numerical examples, presenting the generation of the optimal mesh for simulation of the Step-and-Flash Imprint Lithography (SFIL), the modern patterning process.
9
Content available Graph grammar based Petri net controlled direct solver algorithm
Szymczak A., Paszyński M., Pardo D.
Computer Science
|
2010
|
Vol. 11
65-79
EN
In this paper we present the Petri net setting the optimal order of elimination for direct solver working with hp refined finite finite element meshes. The computational mesh is represented by a graph, with graph vertices corresponding to finite element nodes. The direct solver algorithm is expressed as a sequence of graph grammar productions, attributing the graph vertices. The Petri net dictates the order of graph grammar productions, representing the execution of the solver algorithm over a graph representation of computational mesh. The presentation is concluded with numerical experiments performed for a model L-shape domain.
PL
W artykule przedstawiona została sieć Petriego sterująca kolejnością wykonania produkcji gramatyki grafowej reprezentującej wykonanie algorytmu solvera dokładnego na h adaptowanej siatce metody elementów skończonych. Siatka obliczeniowa przedstawiona została w postaci grafu, którego wierzchołki odpowiadają węzłom elementów skończonych. Algorytm solvera dokładnego wyrażony jest w postaci sekwencji produkcji gramatyki grafowej, atrybutujących wierzchołki grafu. Sieć Petriego określa kolejność wykonania produkcji gramatyki grafowej, reprezentujących wykonanie algorytmu solvera na grafowej reprezentacji siatki obliczeniowej. Artykuł podsumowuje eksperyment numeryczny dotyczący wykonania algorytmu solvera na problemie modelowym w kształcie litery L.
10
Content available remote On the Parallelization of Self-Adaptive hp-Finite Element Methods Part I. Composite Programmable Graph Grammar Model
Paszyński M.
Fundamenta Informaticae
|
2009
|
Vol. 93, nr 4
411-434
EN
The paper presents a general methodology for an efficient parallelization of the fully automatic hp-adaptive Finite Element Method (hp-FEM). The self-adaptive hp-FEM algorithm expressed in terms of the graph grammar productions is analyzed by utilizing the Partitioning Communication Agglomeration Mapping (PCAM) model. The computational tasks are defined over a graph model of the computational mesh. It is done for all parts of the algorithm: the generation of an initial mesh, direct solver (including the integration and elimination of degrees of freedom), mesh transformations (including the h and p refinements), as well as the selection of the optimal refinements. The computation and communication complexities of the resulting parallel algorithms are analyzed. The paper is concluded with the sequence of massive parallel computations. >From the performed tests it implies that the code scales well up to 200 processors
11
Zastosowanie gramatyk grafowych do rozpoznawania i interpretacji diagramów
Szwoch M., Szwoch W.
Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
|
2007
|
T. 13
489-496
PL
W pracy przedstawiono formalizm gramatyk graf owych oraz jego wykorzystanie do rozpoznawania i interpretacji złożonych dwuwymiarowych struktur. Podano przykład zastosowania gramatyki grafowej do interpretacji sche-matów blokowych, formułując specyficzne dla nich reguły produkcji. Pokazano też możliwość zastosowania gramatyk grafowych do wspomagania procesu rozpoznawania oraz interpretacji partytur muzycznych.
EN
In this paper the formalism of graph grammars and their application in recognition and interpretation of 2-dimensional structures is presented. The example of FlowGram graph grammar for flowcharts interpretation is given. Also the possibility of enhancement of optical music recognition and interpretation is presented.
12
Content available remote Inference of Parsable Graph Grammars for Syntactic Pattern Recognition
Flasiński M.
Fundamenta Informaticae
|
2007
|
Vol. 80, nr 4
379-413
EN
A research into a syntactic pattern recognition model based on ( edNLC) graph grammars (introduced and investigated in Janssens and Rozenberg Inform. Sci. 20 (1980), 191-216, and Janssens, Rozenberg and Verraedt Comp. Vis. Graph. Image Process. 18 (1982), 279-304) has resulted in defining the efficient, O(n2), parsing schemes for the ETPL(k) subclass of these grammars and applying it for scene analysis, CAD/CAM object analysis and constructing AI systems (Flasiński Patt. Recogn. 21 (1988), 623-629, Flasiński Comp. Vis. Graph. Image Process. 47 (1989), 1-21, Flasiński Patt. Recogn. 26 (1993), 1-16, Flasiński Comp. Aided-Des. 27 (1995), 403-433, Flasiński Theor. Comp. Sci. 201 (1998), 189-231). In the paper the grammatical inference method for the parsable ETPL(k) graph grammars is defined, completing the development of this syntactic pattern recognition model.
13
Content available remote Grafowe techniki sztucznej inteligencji w percepcyjnej analizie przestrzennych zobrazowań tętnic wieńcowych
Ogiela M., Tadeusiewicz R., Trzupek M.
Acta Bio-Optica et Informatica Medica. Inżynieria Biomedyczna
|
2005
|
Vol. 11, nr 3-4
10-13
PL
W pracy omówiono sposoby wykorzystania technik inteligencji obliczeniowej, a zwłaszcza grafowych formalizmów lingwistycznych do tworzenia syntaktycznego opisu znaczeniowego przestrzennych wizualizacji naczyń wieńcowych serca. Opisy takie mogą być wykorzystywane w inteligentnych systemach wspomagania diagnostyki medycznej, ukierunkowanych na dokonywanie komputerowej interpretacji semantycznej poszczególnych części drzewa naczyń wieńcowych. Interpretacja taka pozwoli na szybką I w znacznym stopniu automatyczną detekcję miejsc istotnych przewężeń światła naczyń. W tym też celu wykorzystane zostały grafowe formalizmy obrazowe, oparte na gramatykach generujących IE grafy, które pozwalają na wykrywanie nieprawidłowości uwidocznionych na obrazach otrzymywanych w trakcie badań diagnostycznych mięśnia sercowego, z użyciem spiralnej tomografii komputerowej. Zaletą omawianych formalizmów obrazowych jest możliwość dokonywania automatycznej Identyfikacji miejsc zmian chorobowych, a także znaczeniowego opisu badanych rekonstrukcji przestrzennych naczyń wieńcowych.
EN
In this paper there will be described the way of application of computational intelligence techniques, and especially graph linguistic formalisms for creation syntactic meaning description of spatial coronary arteries structure. Such descriptions may be than used in intelligent medical diagnosis support systems, which will allow to make essentially steered semantic interpretation of sections coronary arteries morphology as well as fast Identification and automatisation of lumen stricture detection. In order to state a correct diagnosis and define the degree of pathological changes has been used graph image languages based on the expansive graph grammars of IE type. These kinds of grammars enable effective detection of abnormalities in diagnostic images obtained using spiral computerized tomography. An advantage of these Image languages Is automatic identification of changes essential from diagnostic point of view, and the introduction of semantic relations and description In reconstruction of analyzed coronary vessels.
14
Content available remote Distorted pattern recognition and analysis with the help of IE(f] graph representation
Sędziwy A.
Computer Science
|
2002
|
Vol. 4
21-37
EN
An algorithm for distorted pattern recognition is presented. It's generalization of M. Flasiński results (Pattern Recognition, 27, 1-16, 1992). A new formalism allows to make both qualitative and quantitive distortion analysis. It also enlarges parser flexibility by extending the set of patterns which may be recognized.
PL
Praca zawiera algorytm syntaktycznego rozpoznawania obrazów rozmytych (zniekształconych), reprezentowanych przez IE(f) grafy. Jest on uogólnieniem algorytmu parsera dla gramatyk ETPL(k), podanego przez M. Flasińskiego dla obrazów zniekształconych. Zaproponowany formalizm pozwala na ilościową i jakościową analizę rozmycia badanego obiektu.
15
Content available remote Hierarchical graph grammars in graphic print design and generation
Grabska E., Ślusarczyk G., Niewiadomska A.
Machine Graphics and Vision
|
2001
|
Vol. 10, No. 4
519-536
EN
The paper deals with graphic prints in Escher's style and hierarchical graphs. Escher prints are based on regular plane divisions, while hierarchical graphs represent plane division structures. The paper is illustrated by graphic prints generated by the system ESCHER_GRAPHICS.
16
Content available remote Graph grammars and evolutionary methods in graphic design
Hliniak G., Strug B.
Machine Graphics and Vision
|
2000
|
Vol. 9, No. 1/2
5-13
EN
A new approach to image generation being a combination of evolutionary methods and graph grammars is presented. Usually genetic algorithms operate on binary strings. We propose here to use composition graphs as genotypes representing structures of designed objects. Hence, a graph grammar combined with genetic operators constitutes a tool for creating images being phenotypes corresponding to generated graphs. A modified genetic algorithm which uses the graph representation and the graph grammar is described.
17
Content available remote Parsing of random graph languages for automated inspection in statisfical-based quality assurance systems
Flasiński M., Skomorowski M.
Machine Graphics and Vision
|
1998
|
Vol. 7, No. 3
565-623
EN
Basic requirements for an automated visual inspection in intelligent SPC-oriented quality assurance systems are discussed. Extensions of feature IE-graphs representing solids in CAD ([62]) to a stochastic model of manufacturing processes are proposed. An efficient random graph language analysis based on parsable ETPL(k) graph grammars([55)] is presented as a tool for intelligent reasoning in high layer modules of automated inspection systems. The first applications of the model are shown.
18
Content available remote Graphics prints design using graph grammars
Grabska E., Hliniak G.
Machine Graphics and Vision
|
1998
|
Vol. 7, No. 1/2
345-353
EN
The syntactic and semantic aspects of graphic design process are considered. The syntactic structures of prints are represented by graphs. Hence, graph grammars are tools for generation of graph representations of Escher's prints. The possible ways of a realisation of those representations are specified by a realisation scheme which maps into graphic print. The implementation of Escher's prints is also discussed.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.