Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can you give examples of algorithms possessing the following two properties:
1. Solving a non-algebraic problem.
2. Relying on results in algebra.

For example, the paper http://people.csail.mit.edu/nickh/Publications/AlgebraicMatching/Algebraic-SIAM.pdf uses linear algebra to solve graph theoretic problems.

share|improve this question
    
Do algorithms that operate over algebraic structures like groups, monoids, etc. count by your definition? Or do you only want things that directly rely on a result from algebra? –  templatetypedef Jan 10 '12 at 23:54
add comment

6 Answers

Coding theory is full of stuff that fits under this umbrella. For example, the algorithms that allow your scratched CD to play as if the scratch didn't exist rely on Reed-Solomon codes (see e.g. http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction). The properties of the particular codes used in CDs need properties of the field GF(256). Ultimately it relies on the fact that a polynomial of degree $n$ cannot have more than $n$ zeros in a field. IIRC $n=23$ is relevant in the CD-application.

share|improve this answer
add comment

Finding the intersection of two polynomial surfaces, a common problem in Computer-Aided Design, can be done using Gröbner basis techniques.

share|improve this answer
add comment

(Does matrix algebra belong to what "algebra" means here?)

SVD can be applied to text classification.

One can store all document information in matrix $M=(m_{ij})$ (called term-frequency matrix): Each row stands for an article, each column stands for a word, and each entry $m_{ij}$ equals to some kind of word frequency measure (as used commonly, TF–IDF) of the $j$th word in the $i$th article. Perform SVD on matrix $M$ such that $M=U\Sigma V^*$, with the shape like: SVD

, where $U$, $\Sigma$ and $V$ are called term-concept vector matrix, singular values matrix and concept-document vector matrix, respectively. Now each row of $U$ can be viewed as one category of words with similar meanings, whose entries represent correlations (or importance) in the their own category, and each row of $V$ can be viewed as one category of articles with a certain topic, whose entries also act alike. Finally, $\Sigma$ denotes correlations between words and articles.

share|improve this answer
add comment

It occurred to me another one, famous and elementary: Angle trisection problem, which involves field extension

share|improve this answer
3  
Where is the algorithm here? –  Aryabhata Jun 7 '11 at 17:01
    
It proves that there aren't such algorithms so...it can serve as an example for the other side/direction. –  ziyuang Jun 7 '11 at 17:08
    
I see. OP seemed to want algorithms which exist, but I guess it will be useful to other readers. –  Aryabhata Jun 7 '11 at 17:15
add comment

Not strictly algorithmic, but probably the most famous example of algebraic technique in complexity theory is proof of $\mathsf{IP} = \mathsf{PSPACE}$.

A Boolean formula $\phi$ is converted to a multivariate polynomial $p$ over ${\mathbf F}_q$ which agrees with $\phi$ on $\{0,1\}^n$ (nonzero iff true) and to ensure honesty the verifier might evaluate the polynomial at any point of ${\mathbf F}_q^n$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.