CS472/CM472/CS672 Course Project

• Option A (Experimental evaluation):
  
• Pick an application domain that interests you.
• Identify a problem in that application domain that can be formulated as a large linear system.
• Implement and experiment with several techniques to tackle this linear system.
• Option B (Algorithm design):
  
• Identify a class of linear systems for which existing techniques do not scale well.
• Develop a new technique (data structure and/or algorithm) to better tackle this class of linear systems.
• Implement your approach and compare it empirically to other existing approaches.
• Option C (Mathematical Analysis):
  
• Identify a technique for which the mathematical properties (e.g., scalability, stability, convergence) are not well understood.
• Analyze mathematically the properties of this technique.
• Verify empirically the conclusions resulting from your mathematical analysis.

Proposal (no mark)

• Submit by October 9
  
• At most one page
• Which option did you pick?
• Option A:
  
• What is the application domain?
• What is the problem you plan to formulate as a linear system?
• Which techniques do you plan to experiment with?
• Option B:
• What class of linear systems will you design a new technique for?
• What properties would you like this new technique to have?
• Option C:
• What technique do you plan to analyze?
• What properties would you like to analyze/prove about this technique?
  
• Cite 4-8 papers related to the topic of your project that you plan to survey.

Report (50% of assignment marks for CS672 and 5% bonus for CS472/CM472)

• At most 8 pages
• Hand in at the final exam
  

Suggested Structure for the Report

• Option A:
• Introduction
• What is the application domain?
  
• What is the problem? How do you formulate it as a linear system?
• Techniques to tackle the problem
  
• Brief survey of previous work concerning this problem (i.e., the 4-8 papers that you read)
• Brief description of the techniques chosen and why
  
• Empirical evaluation
  
• Compare empirically the techniques for scalability, stability, convergence, ease of use, etc.
• Conclusion:
• What is the best technique?
  
• Is any technique good enough to solve the linear system?
• What future research do you recommend?
• Option B:
• Introduction
• What class of linear systems are you considering?
• Why can't any of the existing techniques effectively tackle this class?
  
• Techniques to tackle the problem
  
• Brief survey of previous work concerning this problem (i.e., the 4-8 papers that you read)
• Describe the technique that you developed
• Brief description of the existing techniques that you will compare to
  
• Empirical evaluation
  
• Evaluate empirically the technique that you developed
• How does it compare to some of the existing techniques?
• Conclusion:
• Can your technique effectively tackle the class of linear systems considered?
• What future research do you recommend?
• Option C:
• Introduction
• What technique are you analyzing?
• What properties did you analyze/prove about this technique?
  
• Analysis
  
• Brief survey of previous work concerning this problem (i.e., the 4-8 papers that you read)
• Describe the analysis performed
  
• Empirical evaluation
  
• Verify empirically the analysis performed
• Conclusion:
• What have you discovered about the technique analyzed?
• What future research do you recommend?