umu.sePublications
Change search
Refine search result
567891011 351 - 400 of 1844
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 351.
    Dahlberg, Timoteus
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Compact Representation and Efficient Manipulation of Sparse Multidimensional Arrays2014Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
    Abstract [en]

    Efficient manipulation of sparse multidimensional arrays, or tensors, is of interest because their decompositions have applications in many different areas. These areas include neuroscience, machine learning, psychometrics, data mining, numerical analysis, and more. This thesis aims to develop the performance-critical parts of a library for manipulating sparse multidimensional arrays by focusing on sorting them in one or more dimensions—a fundamental operation on which many other operations can be built.

    High performance is achieved by tailoring algorithms to a compact representation scheme. Evaluation is done on different algorithms and implementation techniques. The result is shown to be 20 to 70 times faster than qsort in the C standard library. The resulting library is open source.

  • 352.
    Dahlgren Lindström, Adam
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Structured Prediction using Voted Conditional Random FieldsLink Prediction in Knowledge Bases2017Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    Knowledge bases are useful in the validation of automatically extracted information, and for hypothesis selection during the extraction process. Building knowledge bases is a dfficult task and the process is bound to miss facts. Therefore, the existence of facts can be estimated using link prediction, i.e., by solving the structured prediction problem.It has been shown that combining directly observable features with latent features increases performance. Observable features include, e.g., the presence of another chain of facts leading to the same end point. Latent features include, e.g, properties that are not modelled by facts on the form subject-predicate-object, such as being a good actor. Observable graph features are modelled using the Path Ranking Algorithm, and latent features using the bilinear RESCAL model. Voted Conditional Random Fields can be used to combine feature families while taking into account their complexity to minimize the risk of training a poor predictor. We propose a combined model fusing these theories together with a complexity analysis of the feature families used. In addition, two simple feature families are constructed to model neighborhood properties.The model we propose captures useful features for link prediction, but needs further evaluation to guarantee effcient learning. Finally, suggestions for experiments and other feature families are given.

  • 353.
    Danielsson, Karin
    et al.
    Umeå University, Faculty of Social Sciences, Department of Informatics.
    Lindgren, Helena
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Mulvenna, Maurice
    Computer Science, Ulster University.
    Nilsson, Ingeborg
    Umeå University, Faculty of Medicine, Department of Community Medicine and Rehabilitation, Occupational Therapy.
    Waterworth, John
    Umeå University, Faculty of Social Sciences, Department of Informatics.
    Digital technology in healthcare and elderly care2017Conference paper (Other academic)
    Abstract [en]

    The focus of this ECCE 2017 panel is on digital technology in healthcare and elderly care. The discussion concerns the design of technology and the use of technology for health. 

  • 354.
    Dannelöv, Johannes
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Study on Record Linkage regarding Accuracy and Scalability2018Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
    Abstract [en]

    The idea of record linkage is to find records that refer to the same entity across different data sources. There are multiple synonyms that refer to record linkage, such as data matching, entity resolution, entity disambiguation, or deduplication etc. Record linkage is useful for lots of practices including data cleaning, data management, and business intelligence. Machine learning methods include both unsupervised and supervised learning methods have been applied to address the problem of record linkage. The rise of the big data era has presented new challenges. The trade-off of accuracy and scalability presents a few critical issues for the linkage process. The objective of this study is to present an overview of the state-of-the-art machine learning algorithms for record linkage, a comparison between them, and explore the optimization possibilities of these algorithms based on different similarity functions. The optimization is evaluated in terms of accuracy and scalability. Results showed that supervised classification algorithms, even with a relatively small training set, classified sets of data in shorter time and had approximately the same accuracy as the unsupervised counterparts.

  • 355.
    Desmeurs, David
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Algorithms for Event-Driven Application Brownout2015Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    Existing problems in cloud data centers include hardware failures, unexpected peaks of incoming requests, or waste of energy due to low utilization and lack of energy proportionality, which all lead to resource shortages and as a result, application problems such as delays or crashes. A paradigm called Brownout has been designed to counteract these problems by automatically activating or deactivating optional computations in cloud applications. When optional computations are deactivated, the capacity requirement is decreased, which enables low enough response times to obtain responsive applications. Brownout has shown to successfully avoid overloads, however response times are often unstable and they sometimes present spikes due to sudden changes in the workload. This master thesis project is a contribution to the existing Brownout paradigm, to improve it. The goal is to find a way to stabilize response time around a certain set-point by taking the number of pending requests into consideration.

    We designed and implemented new algorithms to improve Brownout and we produced experimental results based on the popular web application benchmark RUBiS. The RUBiS application was modified and deployed on a virtual machine in a Xen environment, and it received requests from emulated clients through a proxy. On this proxy, we first implemented a controller to set a threshold determining if optional computations shall be activated or not in the RUBiS application. Then we investigated machine learning algorithms using an offline training method to be able to set correct thresholds. As an offline training method is not desirable in real environments, we combined the controller and machine learning algorithms, such as using the outputs of the latter as controller feedforward, to obtain satisfying results.

    Experimental results showed that the new Brownout algorithms can improve the initial Brownout by a factor up to 6. We determined this improvement by taking the 95th percentile response times into account, and comparing how far they are on average from a selected set-point. According to this improvement, determining if optional computations shall be activated or not based on queue-length of pending requests is a good approach to keep the response time stable around a set-point.

  • 356.
    Desmeurs, David
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Simulation and analysis of bidding behaviours using agents in online auctions2014In: Proceedings of Umeå's 18th student conference in computing science: USCCS 2014.1 / [ed] Suna Bensch, Thomas Hellström, Umeå: Umeå universitet , 2014, p. 1-9Conference paper (Other academic)
  • 357.
    Desmeurs, David
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Klein, Cristian
    SimScale GmbH.
    Papadopoulos, Alessandro
    Lund University.
    Tordsson, Johan
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Event-Driven Application Brownout: Reconciling High Utilization and Low Tail Response Times2015In: 2015 International Conference on Cloud and Autonomic Computing (ICCAC), New York: IEEE Computer Society, 2015, p. 1-12Conference paper (Refereed)
    Abstract [en]

    Data centers currently waste a lot of energy, due to lack of energy proportionality and low resource utilization, the latter currently being necessary to ensure application responsiveness. To address the second concern we propose a novel application-level technique that we call event-driven Brownout. For each request, i.e., in an event-driven manner, the application can execute some optional code that is not required for correct operation but desirable for user experience, and does so only if the number of pending client requests is below a given threshold. We propose several autonomic algorithms, based on control theory and machine learning, to automatically tune this threshold based on measured application 95th percentile response times. We evaluate our approach using the RUBiS benchmark which shows a 11-fold improvement in maintaining response-time close to a set-point at high utilization compared to competing approaches. Our contribution is opening the path to more energy efficient data-centers, by allowing applications to keep response times close to a set-point even at high resource utilization.

  • 358. Dessouky, Ahmed M.
    et al.
    Taha, Taha E.
    Dessouky, Mohamed M.
    Eltholth, Ashraf A.
    Hassan, Emadeldeen
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Department of Electronics and Electrical Communication Engineering, Faculty of Electronic Engineering, Menoufia University, Menouf, Egypt.
    Abd El-Samie, Fathi E.
    Non-parametric spectral estimation techniques for DNA sequence analysis and exon region prediction2019In: Computers & electrical engineering, ISSN 0045-7906, E-ISSN 1879-0755, Vol. 73, p. 334-348Article in journal (Refereed)
    Abstract [en]

    Bioinformatics is the analysis of biological information using computers and statistical techniques. This paper presents non-parametric spectral estimation techniques based on the Discrete Fourier Transform (DFT) for the analysis of deoxyribonucleic acid (DNA) sequences. These techniques are efficient frequency-domain signal representation techniques, which improve the analysis of DNA sequences and enable the extraction of some desirable information that cannot be extracted from the time-domain representation of these sequences. The adopted techniques are the periodogram, average periodogram (Bartlett), modified average periodogram (Welch), and Blackman and Tukey spectral estimation techniques. The objective of these spectral estimation techniques is to investigate the locations of exons in DNA sequences for gene prediction. A comparison study is presented in this paper between the suggested spectral estimation techniques from the exon prediction perspective. The methods presented in this paper improve the detectability of peaks representing exon regions.

  • 359. Dessouky, Ahmed M.
    et al.
    Taha, Taha E.
    Dessouky, Mohamed M.
    Eltholth, Ashraf A.
    Hassan, Emadeldeen
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Department of Electronics and Electrical Communication Engineering, Faculty of Electronic Engineering, Menoufia University, Menouf, Egypt.
    Abd El-Samie, Fathi E.
    Visual representation of DNA sequences for exon detection using non-parametric spectral estimation techniques2019In: Nucleosides, Nucleotides & Nucleic Acids, ISSN 1525-7770, E-ISSN 1532-2335, Vol. 38, no 5, p. 321-337Article in journal (Refereed)
    Abstract [en]

    This paper presents a new approach for modeling of DNA sequences for the purpose of exon detection. The proposed model adopts the sum-of-sinusoids concept for the representation of DNA sequences. The objective of the modeling process is to represent the DNA sequence with few coefficients. The modeling process can be performed on the DNA signal as a whole or on a segment-by-segment basis. The created models can be used instead of the original sequences in a further spectral estimation process for exon detection. The accuracy of modeling is evaluated evaluated by using the Root Mean Square Error (RMSE) and the R-square metrics. In addition, non-parametric spectral estimation methods are used for estimating the spectral of both original and modeled DNA sequences. The results of exon detection based on original and modeled DNA sequences coincide to a great extent, which ensures the success of the proposed sum-of-sinusoids method for modeling of DNA sequences.

  • 360.
    Dignum, Virginia
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Delft Design for Values Institute, Delft University of Technology, Delft, The Netherlands.
    Ethics in artificial intelligence: introduction to the special issue2018In: Ethics and Information Technology, ISSN 1388-1957, E-ISSN 1572-8439, Vol. 20, no 1, p. 1-3Article in journal (Refereed)
  • 361. Dix, Jürgen
    et al.
    Hegner, StephenUmeå University, Faculty of Science and Technology, Computing Science.
    Foundations of Information and Knowledge Systems, Fourth International Symposium, FoIKS 2006, Budapest, Hungary, February 14-17, 2006, Proceedings2006Conference proceedings (editor) (Refereed)
  • 362. Dix, Jürgen
    et al.
    Hegner, StephenUmeå University, Faculty of Science and Technology, Computing Science.
    Selected Papers From FOIKS (2006): Annals of Mathematics and Artificial Intelligence, Vol. 50, Nos. 1-22007Collection (editor) (Other academic)
  • 363.
    Dmytryshyn, Andrii
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Miniversal deformations of pairs of skew-symmetric matrices under congruence2016In: Linear Algebra and its Applications, ISSN 0024-3795, E-ISSN 1873-1856, Vol. 506, p. 506-534Article in journal (Refereed)
    Abstract [en]

    Miniversal deformations for pairs of skew-symmetric matrices under congruence are constructed. To be precise, for each such a pair (A, B) we provide a normal form with a minimal number of independent parameters to which all pairs of skew-symmetric matrices ((A) over tilde (,) (B) over tilde), close to (A, B) can be reduced by congruence transformation which smoothly depends on the entries of the matrices in the pair ((A) over tilde (,) (B) over tilde). An upper bound on the distance from such a miniversal deformation to (A, B) is derived too. We also present an example of using miniversal deformations for analyzing changes in the canonical structure information (i.e. eigenvalues and minimal indices) of skew-symmetric matrix pairs under perturbations.

  • 364.
    Dmytryshyn, Andrii
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Miniversal deformations of pairs of symmetric matrices under congruence2019In: Linear Algebra and its Applications, ISSN 0024-3795, E-ISSN 1873-1856, Vol. 568, p. 84-105Article in journal (Refereed)
    Abstract [en]

    For each pair of complex symmetric matrices (A, B) we provide a normal form with a minimal number of independent parameters, to which all pairs of complex symmetric matrices ((A) over tilde (B) over tilde), close to (A, B) can be reduced by congruence transformation that smoothly depends on the entries of (A ) over tilde and (B) over tilde. Such a normal form is called a miniversal deformation of (A, B) under congruence. A number of independent parameters in the miniversal deformation of a symmetric matrix pencil is equal to the codimension of the congruence orbit of this symmetric matrix pencil and is computed too. We also provide an upper bound on the distance from (A, B) to its miniversal deformation.

  • 365.
    Dmytryshyn, Andrii
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Skew-symmetric matrix pencils: stratification theory and tools2014Licentiate thesis, comprehensive summary (Other academic)
    Abstract [en]

    Investigating the properties, explaining, and predicting the behaviour of a physical system described by a system (matrix) pencil often require the understanding of how canonical structure information of the system pencil may change, e.g., how eigenvalues coalesce or split apart, due to perturbations in the matrix pencil elements. Often these system pencils have different block-partitioning and / or symmetries. We study changes of the congruence canonical form of a complex skew-symmetric matrix pencil under small perturbations. The problem of computing the congruence canonical form is known to be ill-posed: both the canonical form and the reduction transformation depend discontinuously on the entries of a pencil. Thus it is important to know the canonical forms of all such pencils that are close to the investigated pencil. One way to investigate this problem is to construct the stratification of orbits and bundles of the pencils. To be precise, for any problem dimension we construct the closure hierarchy graph for congruence orbits or bundles. Each node (vertex) of the graph represents an orbit (or a bundle) and each edge represents the cover/closure relation. Such a relation means that there is a path from one node to another node if and only if a skew-symmetric matrix pencil corresponding to the first node can be transformed by an arbitrarily small perturbation to a skew-symmetric matrix pencil corresponding to the second node. From the graph it is straightforward to identify more degenerate and more generic nearby canonical structures. A necessary (but not sufficient) condition for one orbit being in the closure of another is that the first orbit has larger codimension than the second one. Therefore we compute the codimensions of the congruence orbits (or bundles). It is done via the solutions of an associated homogeneous system of matrix equations. The complete stratification is done by proving the relation between equivalence and congruence for the skew-symmetric matrix pencils. This relation allows us to use the known result about the stratifications of general matrix pencils (under strict equivalence) in order to stratify skew-symmetric matrix pencils under congruence. Matlab functions to work with skew-symmetric matrix pencils and a number of other types of symmetries for matrices and matrix pencils are developed and included in the Matrix Canonical Structure (MCS) Toolbox.

  • 366.
    Dmytryshyn, Andrii
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Structure preserving stratification of skew-symmetric matrix polynomials2015Report (Other academic)
    Abstract [en]

    We study how elementary divisors and minimal indices of a skew-symmetric matrix polynomial of odd degree may change under small perturbations of the matrix coefficients. We investigate these changes qualitatively by constructing the stratifications (closure hierarchy graphs) of orbits and bundles for skew-symmetric linearizations. We also derive the necessary and sufficient conditions for the existence of a skew-symmetric matrix polynomial with prescribed degree, elementary divisors, and minimal indices.

  • 367.
    Dmytryshyn, Andrii
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Structure preserving stratification of skew-symmetric matrix polynomials2017In: Linear Algebra and its Applications, ISSN 0024-3795, E-ISSN 1873-1856, Vol. 532, p. 266-286Article in journal (Refereed)
    Abstract [en]

    We study how elementary divisors and minimal indices of a skew-symmetric matrix polynomial of odd degree may change under small perturbations of the matrix coefficients. We investigate these changes qualitatively by constructing the stratifications (closure hierarchy graphs) of orbits and bundles for skew-symmetric linearizations. We also derive the necessary and sufficient conditions for the existence of a skew-symmetric matrix polynomial with prescribed degree, elementary divisors, and minimal indices.

  • 368.
    Dmytryshyn, Andrii
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Tools for Structured Matrix Computations: Stratifications and Coupled Sylvester Equations2015Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    Developing theory, algorithms, and software tools for analyzing matrix pencils whose matrices have various structures are contemporary research problems. Such matrices are often coming from discretizations of systems of differential-algebraic equations. Therefore preserving the structures in the simulations as well as during the analyses of the mathematical models typically means respecting their physical meanings and may be crucial for the applications. This leads to a fast development of structure-preserving methods in numerical linear algebra along with a growing demand for new theories and tools for the analysis of structured matrix pencils, and in particular, an exploration of their behaviour under perturbations. In many cases, the dynamics and characteristics of the underlying physical system are defined by the canonical structure information, i.e. eigenvalues, their multiplicities and Jordan blocks, as well as left and right minimal indices of the associated matrix pencil. Computing canonical structure information is, nevertheless, an ill-posed problem in the sense that small perturbations in the matrices may drastically change the computed information. One approach to investigate such problems is to use the stratification theory for structured matrix pencils. The development of the theory includes constructing stratification (closure hierarchy) graphs of orbits (and bundles) that provide qualitative information for a deeper understanding of how the characteristics of underlying physical systems can change under small perturbations. In turn, for a given system the stratification graphs provide the possibility to identify more degenerate and more generic nearby systems that may lead to a better system design.

    We develop the stratification theory for Fiedler linearizations of general matrix polynomials, skew-symmetric matrix pencils and matrix polynomial linearizations, and system pencils associated with generalized state-space systems. The novel contributions also include theory and software for computing codimensions, various versal deformations, properties of matrix pencils and matrix polynomials, and general solutions of matrix equations. In particular, the need of solving matrix equations motivated the investigation of the existence of a solution, advancing into a general result on consistency of systems of coupled Sylvester-type matrix equations and blockdiagonalizations of the associated matrices.

  • 369.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Dopico, Froilán
    Universidad Carlos III de Madrid.
    Generic skew-symmetric matrix polynomials with fixed rank and fixed odd grade2018In: Linear Algebra and its Applications, ISSN 0024-3795, E-ISSN 1873-1856, Vol. 536, p. 1-18Article in journal (Refereed)
    Abstract [en]

    We show that the set of m×m complex skew-symmetric matrix polynomials of odd grade d, i.e., of degree at most d, and (normal) rank at most 2r is the closure of the single set of matrix polynomials with the certain, explicitly described, complete eigenstructure. This complete eigenstructure corresponds to the most generic m×m complex skew-symmetric matrix polynomials of odd grade d and rank at most 2r. In particular, this result includes the case of skew-symmetric matrix pencils (d=1).

  • 370.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Dopico, Froilán M.
    Universidad Carlos III de Madrid.
    Generic complete eigenstructures for sets of matrix polynomials with bounded rank and degree2017In: Linear Algebra and its Applications, ISSN 0024-3795, E-ISSN 1873-1856, Vol. 535, p. 213-230Article in journal (Refereed)
    Abstract [en]

    The set POLd,rm×n of m×n complex matrix polynomials of grade d and (normal) rank at most r in a complex (d+1)mn dimensional space is studied. For r=1,...,min{m,n}−1, we show that POLd,rm×n is the union of the closures of the rd+1 sets of matrix polynomials with rank r, degree exactly d, and explicitly described complete eigenstructures. In addition, for the full-rank rectangular polynomials, i.e. r=min{m,n} and mn, we show that POLd,rm×n coincides with the closure of a single set of the polynomials with rank r, degree exactly d, and the described complete eigenstructure. These complete eigenstructures correspond to generic m×n matrix polynomials of grade d and rank at most r.

  • 371.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Dopico, Froilán M.
    Departamento de Matemáticas, Universidad Carlos III de Madrid.
    Generic matrix polynomials with fixed rank and fixed degree2016Report (Other academic)
  • 372.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Fonseca, Carlos
    Rybalkina, Tetiana
    Classification of pairs of linear mappings between two vector spaces and between their quotient space and subspace2016In: Linear Algebra and its Applications, ISSN 0024-3795, E-ISSN 1873-1856, Vol. 509, p. 228-246Article in journal (Refereed)
    Abstract [en]

    We classify pairs of linear mappings (U -> V, U/U' -> V') in which U, V are finite dimensional vector spaces over a field IF, and U', are their subspaces. (C) 2016 Elsevier Inc. All rights reserved.

  • 373.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Futorny, Vyacheslav
    Klymchuk, Tetiana
    Sergeichuk, Vladimir V.
    Generalization of Roth's solvability criteria to systems of matrix equations2017In: Linear Algebra and its Applications, ISSN 0024-3795, E-ISSN 1873-1856, Vol. 527, p. 294-302Article in journal (Refereed)
    Abstract [en]

    W.E. Roth (1952) proved that the matrix equation AX - XB = C has a solution if and only if the matrices [Graphics] and [Graphics] are similar. A. Dmytryshyn and B. Kagstrom (2015) extended Roth's criterion to systems of matrix equations A(i)X(i')M(i) - (NiXi"Bi)-B-sigma i = Ci (i = 1,..., s) with unknown matrices X1,, X-t, in which every X-sigma is X, X-T, or X*. We extend their criterion to systems of complex matrix equations that include the complex conjugation of unknown matrices. We also prove an analogous criterion for systems of quaternion matrix equations. (C) 2017 Elsevier Inc. All rights reserved.

  • 374.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Futorny, Vyacheslav
    University of Sao Paulo, Brazil .
    Kågström, Bo
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Klimenko, Lena
    Kiev Polytechnic Institute, Ukraine.
    Sergeichuk, Vladimir
    Institute of Mathematics, Kiev, Ukraine.
    Change of the congruence canonical form of 2-by-2 and 3-by-3 matrices under perturbations and bundles of matrices under congruence2015In: Linear Algebra and its Applications, ISSN 0024-3795, E-ISSN 1873-1856, Vol. 469, p. 305-334Article in journal (Refereed)
    Abstract [en]

    We construct the Hasse diagrams G2 and G3 for the closure ordering on the sets of congruence classes of 2 × 2 and 3 × 3 complex matrices. In other words, we construct two directed graphs whose vertices are 2 × 2 or, respectively, 3 × 3 canonical matrices under congruence, and there is a directed path from A to B if and only if A can be transformed by an arbitrarily small perturbation to a matrix that is congruent to B. A bundle of matrices under congruence is defined as a set of square matrices A for which the pencils A + λAT belong to the same bundle under strict equivalence. In support of this definition, we show that all matrices in a congruence bundle of 2 × 2 or 3 × 3 matrices have the same properties with respect to perturbations. We construct the Hasse diagrams G2 B and G3 B for the closure ordering on the sets of congruence bundles of 2 × 2 and, respectively, 3 × 3 matrices. We find the isometry groups of 2 × 2 and 3 × 3 congruence canonical matrices.

  • 375.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Futorny, Vyacheslav
    University of Sao Paulo, Brazil .
    Sergeichuk, Vladimir
    Institute of Mathematics, Kiev, Ukraine.
    Miniversal deformations of matrices of bilinear forms2012In: Linear Algebra and its Applications, ISSN 0024-3795, E-ISSN 1873-1856, Vol. 436, no 7, p. 2670-2700Article in journal (Refereed)
    Abstract [en]

    Arnold [V.I. Arnold, On matrices depending on parameters, Russian Math. Surveys 26 (2) (1971) 29–43] constructed miniversal deformations of square complex matrices under similarity; that is, a simple normal form to which not only a given square matrix A but all matrices B close to it can be reduced by similarity transformations that smoothly depend on the entries of B. We construct miniversal deformations of matrices under congruence.

  • 376.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Futorny, Vyacheslav
    University of Sao Paulo, Brazil .
    Sergeichuk, Vladimir
    Institute of Mathematics, Kiev, Ukraine.
    Miniversal deformations of matrices under *congruence and reducing transformations2014In: Linear Algebra and its Applications, ISSN 0024-3795, E-ISSN 1873-1856, Vol. 446, no April, p. 388-420Article in journal (Refereed)
    Abstract [en]

    Arnold (1971) [1] constructed a miniversal deformation of a square complex matrix under similarity; that is, a simple normal form to which not only a given square matrix A but all matrices B close to it can be reduced by similarity transformations that smoothly depend on the entries of B. We give miniversal deformations of matrices of sesquilinear forms; that is, of square complex matrices under *congruence, and construct an analytic reducing transformation to a miniversal deformation. Analogous results for matrices under congruence were obtained by Dmytryshyn, Futorny, and Sergeichuk (2012) [11].

  • 377.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Johansson, Stefan
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Kågström, Bo
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Canonical structure transitions of system pencils2015Report (Other academic)
    Abstract [en]

    We investigate the changes under small perturbations of the canonical structure information for a system pencil (A B C D) − s (E 0 0 0), det(E) ≠ 0, associated with a (generalized) linear time-invariant state-space system. The equivalence class of the pencil is taken with respect to feedback-injection equivalence transformation. The results allow to track possible changes under small perturbations of important linear system characteristics.

  • 378.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Johansson, Stefan
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Kågström, Bo
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Canonical structure transitions of system pencils2017In: SIAM Journal on Matrix Analysis and Applications, ISSN 0895-4798, E-ISSN 1095-7162, Vol. 38, no 4, p. 1249-1267Article in journal (Refereed)
    Abstract [en]

    We investigate the changes of the canonical structure information under small perturbations for a system pencil associated with a (generalized) linear time-invariant state-space system. The equivalence class of the pencil is taken with respect to feedback-injection equivalence transformations. The results allow us to track possible changes of important linear system characteristics under small perturbations.

  • 379.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Johansson, Stefan
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Kågström, Bo
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Codimension computations of congruence orbits of matrices, symmetric and skew-symmetric matrix pencils using Matlab2013Report (Other academic)
    Abstract [en]

    Matlab functions to work with the canonical structures for congru-ence and *congruence of matrices, and for congruence of symmetricand skew-symmetric matrix pencils are presented. A user can providethe canonical structure objects or create (random) matrix examplesetups with a desired canonical information, and compute the codi-mensions of the corresponding orbits: if the structural information(the canonical form) of a matrix or a matrix pencil is known it isused for the codimension computations, otherwise they are computednumerically. Some auxiliary functions are provided too. All thesefunctions extend the Matrix Canonical Structure Toolbox.

  • 380.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science. School of Science and Technology, Örebro University, Örebro, Sweden.
    Johansson, Stefan
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Kågström, Bo
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Van Dooren, Paul
    Department of Mathematical Engineering, Université catholique de Louvain, Louvain-la-Neuve, Belgium.
    Geometry of Matrix Polynomial Spaces2019In: Foundations of Computational Mathematics, ISSN 1615-3375, E-ISSN 1615-3383Article in journal (Refereed)
    Abstract [en]

    We study how small perturbations of general matrix polynomials may change their elementary divisors and minimal indices by constructing the closure hierarchy (stratification) graphs of matrix polynomials' orbits and bundles. To solve this problem, we construct the stratification graphs for the first companion Fiedler linearization of matrix polynomials. Recall that the first companion Fiedler linearization as well as all the Fiedler linearizations is matrix pencils with particular block structures. Moreover, we show that the stratification graphs do not depend on the choice of Fiedler linearization which means that all the spaces of the matrix polynomial Fiedler linearizations have the same geometry (topology). This geometry coincides with the geometry of the space of matrix polynomials. The novel results are illustrated by examples using the software tool StratiGraph extended with associated new functionality.

  • 381.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Johansson, Stefan
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Kågström, Bo
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Van Dooren, Paul
    Universite catholique de Louvain, Belgium.
    Geometry of spaces for matrix polynomial Fiedler linearizations2015Report (Other academic)
    Abstract [en]

    We study how small perturbations of matrix polynomials may change their elementary divisors and minimal indices by constructing the closure hierarchy graphs (stratifications) of orbits and bundles of matrix polynomial Fiedler linearizations. We show that the stratifica-tion graphs do not depend on the choice of Fiedler linearization which means that all the spaces of the matrix polynomial Fiedler lineariza-tions have the same geometry (topology). The results are illustrated by examples using the software tool StratiGraph.

  • 382.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå Univ, HPC2N, SE-90187 Umeå, Sweden.
    Kågstrom, Bo
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå Univ, HPC2N, SE-90187 Umeå, Sweden.
    Coupled Sylvester-type Matrix Equations and Block Diagonalization2015In: SIAM Journal on Matrix Analysis and Applications, ISSN 0895-4798, E-ISSN 1095-7162, Vol. 36, no 2, p. 580-593Article in journal (Refereed)
    Abstract [en]

    We prove Roth-type theorems for systems of matrix equations including an arbitrary mix of Sylvester and $\star$-Sylvester equations, in which the transpose or conjugate transpose of the unknown matrices also appear. In full generality, we derive consistency conditions by proving that such a system has a solution if and only if the associated set of $2 \times 2$ block matrix representations of the equations are block diagonalizable by (linked) equivalence transformations. Various applications leading to several particular cases have already been investigated in the literature, some recently and some long ago. Solvability of these cases follow immediately from our general consistency theory. We also show how to apply our main result to systems of Stein-type matrix equations.

  • 383.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Kågstrom, Bo
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Orbit closure hierarchies of skew-symmetric matrix pencils2014In: SIAM Journal on Matrix Analysis and Applications, ISSN 0895-4798, E-ISSN 1095-7162, Vol. 35, no 4, p. 1429-1443Article in journal (Refereed)
    Abstract [en]

    We study how small perturbations of a skew-symmetric matrix pencil may change its canonical form under congruence. This problem is also known as the stratification problem of skew-symmetric matrix pencil orbits and bundles. In other words, we investigate when the closure of the congruence orbit (or bundle) of a skew-symmetric matrix pencil contains the congruence orbit (or bundle) of another skew-symmetric matrix pencil. The developed theory relies on our main theorem stating that a skew-symmetric matrix pencil A - lambda B can be approximated by pencils strictly equivalent to a skew-symmetric matrix pencil C - lambda D if and only if A - lambda B can be approximated by pencils congruent to C - lambda D.

  • 384.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Kågström, Bo
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Orbit closure hierarchies of skew-symmetric matrix pencils2014Report (Other academic)
    Abstract [en]

    We study how small perturbations of a skew-symmetric matrix pencil may change its canonical form under congruence. This problem is also known as the stratification problem of skew-symmetric matrix pencil orbits and bundles. In other words, we investigate when the closure of the congruence orbit (or bundle) of a skew-symmetric matrix pencil contains the congruence orbit (or bundle) of another skew-symmetric matrix pencil. This theory relies on our main theorem stating that a skew-symmetric matrix pencil A-λB can be approximated by pencils strictly equivalent to a skew-symmetric matrix pencil C-λD if and only if A-λB can be approximated by pencils congruent to C-λD.

  • 385.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Kågström, Bo
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Sergeichuk, Vladimir V.
    Skew-symmetric matrix pencils: codimension counts and the solution of a pair of matrix equations2013In: Linear Algebra and its Applications, ISSN 0024-3795, E-ISSN 1873-1856, Vol. 438, no 8, p. 3375-3396Article in journal (Refereed)
    Abstract [en]

    The homogeneous system of matrix equations (X(T)A + AX, (XB)-B-T + BX) = (0, 0), where (A, B) is a pair of skew-symmetric matrices of the same size is considered: we establish the general solution and calculate the codimension of the orbit of (A, B) under congruence. These results will be useful in the development of the stratification theory for orbits of skew-symmetric matrix pencils.

  • 386.
    Dmytryshyn, Andrii
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Kågström, Bo
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Sergeichuk, Vladimir V.
    Ukrainian Acad Sci, Kiev, Ukraine.
    Symmetric matrix pencils: codimension counts and the solution of a pair of matrix equations2014In: The Electronic Journal of Linear Algebra, ISSN 1537-9582, E-ISSN 1081-3810, Vol. 27, p. 1-18Article in journal (Refereed)
    Abstract [en]

    The set of all solutions to the homogeneous system of matrix equations (X-T A + AX, X-T B + BX) = (0, 0), where (A, B) is a pair of symmetric matrices of the same size, is characterized. In addition, the codimension of the orbit of (A, B) under congruence is calculated. This paper is a natural continuation of the article [A. Dmytryshyn, B. Kagstrom, and V. V. Sergeichuk. Skew-symmetric matrix pencils: Codimension counts and the solution of a pair of matrix equations. Linear Algebra Appl., 438:3375-3396, 2013.], where the corresponding problems for skew-symmetric matrix pencils are solved. The new results will be useful in the development of the stratification theory for orbits of symmetric matrix pencils.

  • 387.
    Dobson, David
    et al.
    Department of Mathematics, University of Utah, Salt Lake City, USA.
    Wadbro, Eddie
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Optimization of transmission spectra through periodic aperture arrays2011In: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 12, no 4, p. 509-534Article in journal (Refereed)
    Abstract [en]

    We investigate the problem of designing periodic aperture arrays in a thin, perfect electric conductor, such that transmission energy of time-harmonic electromagnetic plane waves through the apertures attains a specified profile with respect to frequency. We first formulate a mathematical model for the electromagnetic transmission problem, and describe a regularized numerical discretization. We then formulate the design problem as a mathematical optimization in which an objective is minimized with respect to a discrete characteristic function describing aperture shape and topology. A level-set method combined with a filtering technique and a gradient-based minimization algorithm numerically solves the problem. Several numerical examples are presented which show that although it is possible to obtain improved transmission spectra, the problem is underposed and subject to numerical instability.

  • 388.
    Drewes, F.
    Umeå University, Faculty of Science and Technology, Departement of Computing Science.
    The complexity of the exponential output size problem for top-down and bottom-up tree transducers2001In: Information and Computation, Vol. 169, no 2, p. 264-283Article in journal (Refereed)
    Abstract [en]

    The exponential output size problem is to determine whether the size of output trees of a tree transducer grows exponentially in the size of input trees. In this paper the complexity of this problem is studied. It is shown to be NL-complete for total top-down tree transducers, DEXPTIME-complete for general top-down tree transducers, and P-complete for bottom-up tree transducers, (C) 2001 Academic Press.

  • 389.
    Drewes, F.
    Umeå University, Faculty of Science and Technology, Departement of Computing Science.
    Tree-based generation of languages of fractals2001In: Theoretical Computer Science, Vol. 262, no 1-2, p. 377-414Article in journal (Refereed)
    Abstract [en]

    The notion of P-interpreted top-down tree generators is introduced, combining the nondeterministic nature of grammars as known from formal language theory with the infinite refinement of pictures studied in fractal geometry. (C) 2001 Elsevier Science B.V. All rights reserved.

  • 390.
    Drewes, F.
    Umeå University, Faculty of Science and Technology, Departement of Computing Science.
    Tree-based picture generation2000In: Theoretical Computer Science, Vol. 246, no 1-2, p. 1-51Article in journal (Refereed)
    Abstract [en]

    The concept of tree-based picture generation is introduced. It is shown that there are equivalent tree-based definitions of four picture-generating devices known from the literature, namely collage grammars, iterated function systems, context-free chain-code grammars, and OL-systems with turtle interpretation. Furthermore, generalisations of each of these systems are discussed. (C) 2000 Elsevier Science B.V. All rights reserved.

  • 391.
    Drewes, F.
    et al.
    Umeå University, Faculty of Science and Technology, Departement of Computing Science.
    du Toit, C.
    Ewert, S.
    van der Merwe, B.
    van der Walt, A.
    Bag Context Tree Grammars2008In: Fundamenta Informaticae, Vol. 86, no 4, p. 459-480Article in journal (Refereed)
    Abstract [en]

    We introduce bag context as a device for regulated rewriting in tree grammars. Bag context represents information that is not part of a developing tree, but instead evolves separately during a derivation. We present several results. First, we give some normal forms and equivalent formulations for bag context tree grammars. Then we compare bag context tree grammars to their random context counterparts. We show that bag context is strictly more powerful than random context; in doing so, we show that the class of bag context tree languages is the closure of the class of random context tree languages under linear top-down tree transductions. Finally, we consider the structural limitations of bag context tree grammars. We establish a necessary condition for languages generated by bag context tree grammars, and use it to present a tree language that cannot be generated by such a grammar. Moreover, we show that the class of bag context tree languages is incomparable with the class of branching synchronization tree languages.

  • 392.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    DAG automata for meaning representation2017In: Proceedings of the 15th Meeting on the Mathematics of Language (MoL 2017) / [ed] Makoto Kanazawa, Philippe de Groote, Mehrnoosh Sadrzadeh, 2017, Vol. W17-34, p. 88-99, article id W17-3409Conference paper (Other academic)
    Abstract [en]

    Languages of directed acyclic graphs (DAGs) are of interest in Natural Lanuage Processing because they can be used to capture the structure of semantic graphs like those of Abstract Meaning Representation. This paper gives an overview of recent results on a family of automata recognizing such DAG languages.

  • 393.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Delegation Networks2007Report (Other academic)
    Abstract [en]

    We introduce a generalization of tree-based generators called delegation networks. These make it possible to generate objects such as strings, trees, graphs, and pictures in a modular way by combining tree-based generators of several types. Our main result states that, if all underlying tree generators generate regular tree languages (or finite tree languages), then the tree-generating power of delegation networks is the same as that of context-free tree grammars working in IO mode.

  • 394.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Departement of Computing Science.
    From Tree-Based Generators to Delegation Networks2007In: Proc. 2nd International Conference on Algebraic Informatics, 2007, p. 48-72Conference paper (Refereed)
  • 395.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Computing Science.
    Grammatical Picture Generation: A Tree-Based Approach.2006Book (Other academic)
  • 396.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Implementation and application of automata: 20th international conference, CIAA 2015, Umeå, Sweden, August 18-21, 2015, Proceedings2015Conference proceedings (editor) (Other academic)
  • 397.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Computing Science.
    Links2007In: International Journal of Foundations of Computer Science, Vol. 18, p. 1187-1196Article in journal (Refereed)
  • 398.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    MAT Learners for Recognizable Tree Languages and Tree Series2009In: Acta Cybernetica, Vol. 19, no 2, p. 249-274Article in journal (Refereed)
  • 399.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Millstream systems and graph transformation for complex linguistic models (Extended abstract)2013In: Descriptional Complexity of Formal Systems: 15th International Workshop, DCFS 2013, London, ON, Canada, July 22-25, 2013. Proceedings / [ed] Helmut Jurgensen, Rogério Reis, 2013, p. 14-16Conference paper (Refereed)
    Abstract [en]

    Allan Turing [5] suggested to regard the ability to communicate in human language as an indication of true intelligence. If a computer would be able to engage in such a communication with human beings without them being able to identify the computer, the computer should be considered to be intelligent. Although it is debatable whether this conclusion could really be drawn from the Turing test (see also [6]), it shows how complex human language is and how many facets it has. Some of the most important dimensions of language are phonology, morphology, syntax, semantics, and pragmatics. Pragmatics includes the whole field of contextual and ontological knowledge. These dimensions are not orthogonal, but are intertwined in many ways. Even if we restrict ourselves to text input and output, thus disregarding phonology, this creates an amazingly complex structure. While computational linguists try to make progress understanding the relation between the various dimensions, we usually restrict ourselves to syntax in natural language processing, sometimes extended by limited attempts to make a semantic interpretation or to make use of ontological knowledge. The reason for this is, of course, the descriptional and computational complexity of the models required.

  • 400.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    On DAG Languages and DAG Transducers2017In: Bulletin of the European Association for Theoretical Computer Science, ISSN 0252-9742, Vol. 121, p. 78p. 142-163Article in journal (Other academic)
    Abstract [en]

    We review recent results regarding DAG automata and regular DAG languages and point out some open problems that may be interesting to work on. Moreover, a notion of DAG transducers is suggested.

567891011 351 - 400 of 1844
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf